What to use for space in REST URI?

I like using "_" because it is the most similar character to space that keeps the URL readable.

However, the URLs you provided don't seem really RESTful. A URL should represent a resource, but in your case it represents a search query. So I would do something like this:

/people/{first}_{last}
/people/{first}_{last}_(2)  - in case there are duplicate names

It this case you have to store the slug ({first}_{last}, {first}_{last}_(2)) for each user record. Another option to prepend the ID, so you don't have to bother with slugs:

/people/{id}-{first}_{last}

And for search you can use non-RESTful URLs:

/people/search?last={last}&first={first}

These would display a list of search results while the URLs above the page for a particular person.

I don't think there is any use of making the search URLs RESTful, users will most likely want to share links to a certain person's page and not search result pages. As for the search engines, avoid having the same content for multiple URLs, and you should even deny indexing of your search result pages in robots.txt

Why not use + for space?

I am at a loss: dashes, minuses, underscores, %20... why not just use +? This is how spaces are normally encoded in query parameters. Yes, you can use %20 too but why, looks ugly.

I'd do

/personNamed/Joe+Blow

You could always just accept spaces :-) (querystring escaped as %20)

But my preference is to just use dashes (-) ... looks nicer in the URL. unless you have a need to be able to essentially query in which case the last example is better as you noted