Try a commerical database, such as Microsoft SQL Server (FD: I work there as a developer). To bring up a recent example, it can build indexes without locking the whole table so you wouldn't need to jump throught the hoops like the FriendFeed guys just did with MySQL. Unless your time is free it will cost you less to buy SQL Server than to write your own "online index thingie" on top of MySQL.
And if your time is free, then you are probably a startup and you can get SQL Server and bunch of other MS tools for free via http://www.microsoft.com/BizSpark/
MySpace runs on SQL Server: http://www.sqlservercentral.com/blogs/steve_jones/archive/20... and if it's good enough for them it will likely be good enough for your site as well. I'm not sure if the scale-out story is any good (there are "partitioned views" which are basically "sharding" but I never used those), but scale-up story is as good as they come - it can efficiently utilize 64-cores of the HP superdome.
I don't know much about Oracle and IBM DB2, but I know that the latter has a free version without too many restrictions on it, so give them a spin as well. If ease of use is importnat to you, common wisdom has it that Microsoft's is the easiest to use among the top commercial vendors. NB: I did not verify the common wisdom, YMMV :-)