Depends on what the startup will do - desktop?, web?, embedded (cellphone)? It also depends on how complicated your data model will be. If the data model is simple (a few tables) then it really doesn't matter which database you pick because you'll probably be able to switch databases if necessary. I'm guessing you're needs aren't that complicated since you are even considering Amazon's SimpleDB. If you're a one man startup or very small, I'd pick the database you seem to learn the fastest or are most comforatable with - at least to build a prototype with. If that's not the case, the skillset of the pool of potential hires is probably important.
Does a relational database even fit the need - maybe just storing a data structure in the language you're building the software in will do the trick? - otherwise you'll have to make choices on how best to get the data from a database into your application - and back again. These choices bring up the whole "impedance mismatch" problem:
http://en.wikipedia.org/wiki/Object-Relational_impedance_mismatch
For desktop and embedded, the simple, free SQLite is popular, even with big companies:
http://www.sqlite.org/famous.html
(Integrates well with C, Python, etc)
For the web, MySQL is very popular but PostgreSQL (with its awkward name yet powerful, mature Oracle-like features would be a good choice too) - both are FREE by the way.
There's even a small-scale version of Oracle that's FREE (Oracle Database XE) but it's limited to 4GB of user data and 1GB RAM - you can match it up a free, quick "app builder" of sorts: "Oracle Application Express" but if you out grow that you'll either have to pay for licenses or switch databases.
http://www.oracle.com/technology/products/database/xe/index.html
See the source below for tables comparing many more databases.