Magento kräver väldigt mycket ram minne.
Men några som jag vet erbjuder just magento hosting är egensajt.se "dannielos him self"
Sen tror jag nog istället du bör kolla på en egen VPS eftersom du dels behöver mycket minne sen vill du även att applikationen ska gå fort och då lär du involvera memcached och andra saker. Så jag tror faktiskt du inte ska välja webbhotell i de fallet.
Dock kan du slå ett öga på
http://www.webhosting-benchmark.com/rank
Där finns en lista där du kan se vilka webbhotell som ger mest prestanda för pengarna. Sen är ju kanske inte alla test realistiska men jag tror ändå det kan vara rätt väg att gå.