I'd suggest calling hosting companies and talk to a sales rep. Your situation is uncommon, so avoiding the "package deal" pricing schemes might get you a much better deal that fits better. Limits like 1GB databases are usually just arbitrary price tags set by marketing anyway, a sales rep will be more flexible. They might not bend very far for under $20/month, but it's worth a try.
I'm a big fan of the non-managed VPS hosts like Linode, but wouldn't recommend it unless you really know your way around a web server - installing & configuring all the software, handling kernel upgrades, configuring iptables, disabling root, etc. You could be setting yourself for a lot of problems otherwise.
And assuming "easier mod_rewrites" means easier syntax, see if mod_alias can do what you need. The only other implication of "easier" I can think of is if your host just forbids them. In that case, just about any other host will be easier.