tu t'attends vraiment à avoir une réponse un samedi sur un forum pro ? ...
(le up est pas autorisé par ailleurs)

C'est le WE en même temps.  
Quel(s) opérateur(s) pour tes 2 lignes Internet ?
Il te faut un routeur prenant en compte le protocole VRRP, ce dernier te permettra de mettre en place une redondance, Si les routeurs sont gérer par l'opérateur c'est lui qui te mettra ça en place, sinon ce sera à toi de le faire.
Pour la QoS, même chose, soit l'opérateur le fait dans les routeurs, soit tu le fais. Pour cela il te faudra marquer tes paquets.Les téléphones IP proposent le plus souvent des options pour marquer les flux (valeur DSCP du SIP = CS3, pour la voix = EF), tes routeurs devront êtres configurés pour prendre en compte la QoS (et éventuellement marquer les paquets s'ils ne le sont pas en amont). A noter aussi que les réseaux opérateurs utilisent pas mal le MPLS, donc plus de niveau 3 mais du niveau 2 (2.5 pour les puristes), on ne parle plus de QoS mais de CoS (Classe de Service), rassures toi il y a une table de conversion.
Pour tes tél en POE, bin il te faut un switch POE.    
Pour le firewall, tu as plus que l'embarras du choix, autant partir sur du gratuit donc de l'Open source.

+1 mais par contre ton budget est limite un switch POE ça peut déjà pas mal chiffrer.

Si il veux 35 tels en POE il faut donc un switch 48 ports POE, ce qui reviens à un truc de ce genre: http://www.ldlc.com/fiche/PB00188109.html
déja 1000€...