My recommendations are going to be a bit off from the usual fare I imagine.
Shinobido Takumi- Essentially it's a bunch of missions with Tenchu style gameplay and a pretty neat physics engine. JP knowledge is minimal and once you get past the horrid framerates and overall mediocre graphics it's fun stuff. Not sure if you can get it on the cheap anymore though :/. Oh and it's also an add-on pack for Shinobido Imashime. Apparently Imashime has a UK release but unless it supports 60hz I can't purchase it. There's a mission editor too in Takumi, it's kind of neat to mess with although all I usually end up doing is making a bunch of bears maul random people.
Tsukiyo Ni Saraba- Max-Payne-style shooter where you can go into bullet-time to take out bunches of thugs and a handful of weird and wacky bosses. The controls are a bit iffy at first and getting far in the game requires timing your gunshots so that you deliver critical hits often. Got a PAL release I believe by the name of 1,000 Bullets.
Sega Ages: Dynamite Deka- Really nice remake of Die Hard Arcade(or Dynamite Deka in Japan). The new modes change up gameplay in many interesting ways(though they're incredibly difficult as there are no continues). Altered Beast mode for example as you running around as some werewolf and you have to constant grab orbs dropped by enemies to keep your life up. There's also a mode where gunshots are instant kills, and a handful of others. The main game is great fun and the enhanced graphics are pretty nice. Also yeah you play as Bruce Willis, even the box-art confirms it.
NamCollection: One of the stranger compilations I've seen. The set includes the PSX versions of Tekken 1, Ace Combat 2, Ridge Racer 1, Klonoa, and Mr. Driller. Course I got this at a nice price(19.99) so YMMV. As far as the games are concerned even Ace Combat 2 is in full english. Mr. Driller is fairly easy to understand and everyone in Klonoa speaks in their wacky moon language anyway so no big deal.
Monster World Collection: The nice thing about this set is that the US versions are included for most of the games so you can play them in english. Monster World IV unfortunately never had a US release, but at least it's fairly easy to get into and you'd only need an FAQ for a handful of parts.
Treasure Box: Gunstar Heroes, Dynamite Headdy, and Alien Soldier in a single compilation. Alien Soldier alone would run for close to $175 or more on yahoo auctions/ebay so yeah..for less than $30 you can't go wrong on this set. US/PAL versions are included of course, though I prefer the JP version of Dynamite Headdy(more continues for one thing).
Fighting games: Neogeo Battle Coliseum, KoF XI, Samurai Spirits Tenkiachi, Darkstalkers Collection, Guilty Gear Slash/Accent Core, Hokuto-No-Ken, well..you get the idea. An import PS2 is required if you're a fan of 2D fighters.
2D shooters: ESPGaluda, Dodonpachi Daijouou, Ibara, Mushihime, and more.
Taito Memories: There are four sets out now(two of them are budget-priced) and they cover Taito's arcade history quite well. Elevator Action Returns, Darius Gaiden, and more are available through these really nice compilations. Though personally I wouldn't recommend these sets unless you're a huge fan of Taito games already. I like pretty much everything they've done so eh...
Oh and EDF2 is of course required. The framerate is worse but in many ways it's a better game than the X360 release of EDF3/EDF2017. For one there's an additional character to play as who uses a jet pack and more sci-fi type weaponary. There's also 20-30(?) more stages to play and a bunch of monsters that didn't make it into EDF3.
If you don't own an X360(and thus EDF3) there is no excuse for not purchasing this game.
Oh and I found an old thread the OP might be interested in:
http://www.neogaf.com/forum/showthread.php?t=137501
A few more recommendations there.