C/Golang/Lua/Vala/SBCL/Ada/Pascal and an embedded datastore like bdb!
Why in my day we used to write little apps with C and bdb that used less than 5mb of memory! (Sqlite didn't exist yo.)
Heck these days you get (ENTERPRISE) choices like LevelDB and BangDB.
Edit: Who wants to have a datastore-backed c10k contest on prgmr machines? :D
I was trying to be lean.
Ruby users are quiche eaters anyway. Real programmers write their code in Fortran and persist to a hierarchical database on a mainframe.
You think real programmers need needles.
Or hands.
Depends on what you call modern.
I think fitting nginx / embedded lua / redis should be possible (considering your dataset fits into 32 megs).
Actually, that sounds like an interesting challenge!
In my experience on Rackspace cloud 512MB instances are the minimum you should use for tiny production apps. Also, they're discontinuing 256MB on OpenStack - these were suitable for single-user dev instances, but I got more swap and or locking if ever attempting to run publicly with traffic. 512MB instances solved that issue.
Edit: Also I should mention I'm assuming you mean wanting to run a fairly standard stack, not a stack targeted toward tiny memory footprint.
Domain: or get something longer for $9. E.g., authyapp.com or getauthy.com
Design: http://themeforest.net/ $15-$25, or DIY (depends on how much design matters for your niche--for Pinboard it clearly doesn't)
Video: You don't need no stinkin' video
Hosting: Maciej is recommending http://prgmr.com/xen/ for $32 (but can you actually run a modern app stack on just 128 MB of RAM?) Anyway, even if you need a gig, that's $100.