Where are you going for Mono hosting?
Solution 1:
http://mono-project.com/FAQ:_ASP.NET#Hosting
Solution 2:
Try Ubiquity Hosting
Their linux plans include Mono by default...
Solution 3:
Definitely get a VPS (Linode, Rimuhosting, etc) and install mono yourself. Shared hosting and mono don't make sense together for many reasons.