Here are a few previous discussions on Stack Overflow:
Solr is the larger and older project, and may have more/better support for advanced search features down the road, but for the case you describe, it's a tossup. It comes down to a choice between the Sunspot Solr client and the Thinking Sphinx client, both of which are excellent.
I can certainly put in an endorsement for the Websolr addon on Heroku, but it's a bit biased because I run it ;) In fact, ours was one of the first Heroku addons launched, back in the summer of 2009.