Solr search vs database search

>And if it isn't, how do I get it to run on a live site - will I have to pay some Solr service provider (such as Acquia) or are there free services?

Usually, one hosts its own solr server e.g. on a dedicated server. Acquia search currently doesn't work with the eRecruiter as it uses the search_api, for which acquia search has currently no support. I don't think there are free hosted solr servers.

>is it possible to remove that dependence?
You can reconfigure the search api easily to use a DB server or another one instead of the pre-configured solr server. However, I'm not sure whether there is already facet support in the search api DB backend available.

Anyway, Solr is the more powerful search backend, so for medium to bigger sites it makes sense anyway.

DB backend supports facets, yep.
Solr is waaaaaay better though, so stick with it if you can set it up.
See http://zugec.com/73-how-setup-search-api-apache-solr for a pretty decent guide.

A site like linode can offer a VPS where you can set up a LAMP with apache solr. You are the admin to your own server. You can build anything you want. This is a link to the site if you decide to try them. It has my referral code included ;-). I have been working at getting this to work for a couple weeks. Ping me if you give it a try.

http://www.linode.com/?r=d6cb9ddc89d8c49e018f3835e60c2ca235eff05c

I also plan to use eRecruiter, but my host does not support Solr. Will I still be able to use eRecruiter?

Yes but in a limited way, you can use the Database Search backend of Search API (which is buggy) or you can disable the Advanced recruiter search features all together.

The rumor is that Acquia is working on a hosted Solr server that works with Search API module. There are a couple of other companies that offer hosted Solr server for the Solr Search Integration module. I think if people are interested and call them up they will configure a server for the Search API module too. Right now they probably don't that there is demand for the service. Here is a relevant discussion on Drupal Answers.

(Disclaimer: I am the owner of Midwestern Mac, LLC)...

Midwestern Mac, LLC also offers hosted Apache Solr search, and supports both Apache Solr Search Integration and Search API (which this install profile uses). There are a few eRecruiter sites already using our services, and we'd love to help more people get it set up.

As Shadlington says, Solr is WAAAAY faster (and more flexible, to boot), and if it takes a little time to get it set up (on your own server, through Acquia, or through MM), it's well worth the effort.

for usability reasons we are planning to release recruiter with the search api database backend and have solr as an optional extension for performance reasons.

The Solr backend is now optional. After the initial installation the Search API database backend is going to be used. Only if people activate the recruiter_search_solr module, the resume and job search are going to use Solr.