Non mi sembrano dei requisiti particolamente strani, la combinazione linux/apache/PHP/mysql è una di quelle più diffuse.
Come ti dicevo prima guarda le garanzie che ti danno sulla banda, lo spazio web illimitato (o molto elevato) ti serve solo se devi fare un ftp server o devi gestire grandi quantità di immagini.
Comunque un buon punto per iniziare le tue ricerche è questo:
hosting.html.it
_____________________________________
Good evening, there was already an injury, huh?
Giovanni Trapattoni, falling off his chair