Mit Server4you.de machen wir derzeit gute Erfahrungen. Die Server sind schnell und haben eine gute Anbindung. Soweit ich weiß, bestanden allerdings nur ein paar kleinere Probleme mit der Linux-Distro die vorinstalliert wurde, oder ich werf gerade was durcheinander.
Schau dir mal dieses Angebot an:
http://www.server4you.de/de/d/showplan.php?products=0

Die Punkte die man kritisch betrachten sollte bei der Serverwahl sind der Traffic inklusive, Prozessor(en) und der RAM.
Anbindung ist eh meistens 100 MBit, oder sollten es sein (Sagonet kann ich da nicht empfehlen, die bescheißen einen um die Bandbreite),
Wie viel Traffic ihr braucht, hängt stark von dem Projekt ab.
Squarenet braucht einen Server dessen Traffic an den Terrabytebereich herankommt (750-1000 GB und das ohne Downloads). Das liegt daran das Squarenet nunmal sehr bekannt und stark frequentiert ist (rund 10000 Unique Visits/Tag).
Umso mehr RAM drinsteckt, umso weniger wird der Prozessor belastet. 1 GB ist da eigentlich schon fast standard, aber ~500MB ist auch ok wenn der Prozessor ordentlich ist.
Der Prozessor wird hauptsächlich im Zusammenhang mit PHP und MySQL belastet. Große Forensysteme hauen da besonders rein. Dieses Forum benötigt mind 2GHz oder DUAL mit mind. 1 GHz je. Dieser Forenserver hat allerdings 2 GB RAM weshalb da noch einiges drin ist.
Nur-Downloadserver hauen da kaum auf den Prozessor eher auf den Traffic.

Ganz wichtig bei der Sache ist allerdings das einer von euch sich mit Remote-Systemadministration auskennt, denn an den Servern müsst ihr selbst schrauben. Das Einzige, dass das Rechenzentrum für euch tun kann, ist ein hard-reboot und eine Reinstallation der Distro wenn das System einmal absolut tod ist.

Ahja, Domains sind AFAIK nicht inklusive, aber wenn ihr schon einen server mieten wollt, könnt ihr euch auch selbst Domains beschaffen und diese auf den Server routen.