We went to nethosted before we ended up here. They set up some temporary hosting for us to try but they didn't like the size of our database so turned us away. This was quite a while ago, although I doubt things have changed too much.
I don't mind moving hosts again, I've got the whole process down to a fine art now with upgrading, backups, restores etc. So long as where ever we go to has SSH and root access so I can make use of the CLI tools, upgrade and fiddle with MySQL etc., I'm happy.