Check the ec2onrails mailing list, where there has been a lot of discussion of the various thin/nginx/passenger/apache alternatives and permutations, plus some hard data posted based on some decent tests.
You'll also find a nice packaged RoR/Ubuntu stack in the shape of the ec2onrails image (google ec2onrails) - it's for running on the amazon EC2 cloud but it's got a lot of nice stuff in there + capistrano tasks. Currently it's based on apache, but the version in progress is looking at the alternatives. No reason you couldn't use the same build script for a non EC2 server.
If your problem is simply the initial requests, try warming your server up before considering it live (e.g. by running a script to automatically exercise the basic operations).
Oh and I should add - are you sure the problem is your stack? More likely it is your code. It may be worth seeing where your bottlenecks are first and what you can get out of caching, improved queries and indexing, and especially memcached before tweaking anything else.