Hi MOH,
Leaving aside the issue of Magento vs Everything Else, and focusing on the question - we've seen Magento running on different shared servers in Ireland and the performance is only acceptable to poor.
If you have an ordinary enough sized store that will be left fairly static it's fine - but don't try anything like bulk imports, and exports of the catalogue - bulk changes in products etc (basically - standard enough techniques for managing a catalogue on a regular basis).
So you can set up and run a small shop which sells products that you are going to be updating yourself manually. The performance of the store will be okay. I won't name names, because I can't recommend a specific Irish host for Magento hosting.
By the by, VPS hosting isn't a silver bullet at all - you'll need to get it configured and set up for hosting a Magento site, which of course will cost you. Out of the box a VPS solution is going to be worse than any of the decent Irish shared server solutions.
If you're happy to go abroad - then Medialayer in the states offer an excellent service at good value - starting at approx. $10 a month. If you need someone closer to home - we've also used Xtrahost in the UK - more expensive (I think maybe in the region of 40 or 50 a month) and they have some quirks - they don't give you access to a control panel for example - you need to make configurations via support...
Finally, the best of the best close to home and abroad has to be Rackspace - but if you had the money for those guys you wouldn't be here asking questions
I notice your post is fairly old now - so have you any experience to share? Who did you go with in the end?