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.