Ideal database for geo (map) data

PostGIS might be the best choice. Note: PostGIS is PostgreSQL with geo-extensions. You literally install postgres, and then run various scripts which add in geo functions and types.

See the OpenStreetMap information about PostGIS. you can load OpenStreetMap planet files/planet extracts, into PostGIS using osm2pgsql, and this is what is done on the OpenStreetMap tile server, where the Mapnik renderer runs. However...

There is also a more raw database schema for OpenStreetMap data (tables called "nodes" and "ways" etc) This is what main OpenStreetMap database server uses for storing its geo-data and allowing edits over an API. This isn't so clever when it comes to spatial indexing etc, but nice and simple. You can create a database in this format by installing the OpenStreetMap API/website ruby on rails code. This is the most reliable way of setting up an up-to-date version of the database schema (defined by the rails migrations). After that you might run the osmosis tool to populate the database.

I'd recommend with PostGIS 1.5 using the geography type as it's suited to what you want, however my only concern with using something like this on an embedded device would be memory usage.

I've built something vaguely related using a non GIS database (firebird) in Java and the performance was more than adequate for retrieving points within a bounding box (although fancy SQL was required which isn't the case with PostGIS).