Totally agree with:
Dead Space Extraction
No More Heroes
Okami
de Blob
Excitebots
House of the Dead: Overkill
Boom Blox Bash Party
Madworld
Resident Evil 4
Zack & Wiki
But I'll try to add some great budget games not already mentioned, along with the prices I've seen them at recently in Canada. These games won't appeal to everyone so read a review or two before deciding. If any are in a genre you enjoy then they are probably worth consideration!
Dawn of Discovery ($10-20)-- If you like Civilization-style building games, this is a no-brainer. Very well made, although the lengthy tutorial (aka: "story mode") is a bit slow paced. Free play is where it's at!
Little King's Story ($20-25) -- Great quality, and very funny. Look past the "kiddie" graphics and you'll find a lot to love. One of last years most overlooked gaming gems, it's now totally affordable too.
Pinball Hall of Fame: Williams Collection ($10-$20) -- Pinball is obviously a niche attraction, but this game offers tremendous value and is very well made. (The PS3/360 versions are probably a better choice if you have that option.)
Samba de Amigo ($5-$10) -- The controls aren't good, but not as bad as some people say. They don't work well enough to master advanced levels, but are enough to enjoy the lower levels. Fun party game, and for $5 used at EB Games you can't argue the price.
Sam & Max: Season 1 ($5-$15) -- Classic point-and-click adventure, with a good sense of humor. The second season is supposed to be released soon.
Geometry Wars Galaxies ($10-20) -- The base game is a very simple arcade experience, but dozens of unique levels expand on that concept and continually add new challenges. Perfect for high-score challenges, if that appeals to you.
Lego Star Wars: The Complete Saga ($20-$25) -- Very simple gameplay, but good co-operative action with TONS of content and a popular theme. Good choice if your fiance is into Star Wars. (Note: Batman and Indiana Jones versions are also good choices if those themes appeal more.)
Final Fantasy Fables: Chocobo's Dungeon ($20-25) -- Extremely cute rogue-like RPG with a lot more depth than you would expect from first appearances. Not for everyone, but great value if this is your type of game.
Dokapon Kingdom ($25-30) -- A party game based around an RPG board-game. Sort of like Mario Party, but with more strategy and less mini-games... sort of like Talisman (if you ever played that old board game), but with more hilarious things players can do... This is a hard game to describe, but can be extremely fun with the right group of people.
Trauma Center ($20-30) -- Either Second Opinion or New Blood are worth getting. New Blood is ridiculously hard at times, but has 2-player co-op. Mixing an anime-style ER drama with some of the best use of the Wii remote I've seen, these games are definitely unique. There is another sequel called Trauma Team coming soon that looks even better though.
Edit: Two other games that might be worth considering include Ghost Squad and Resident Evil: The Umbrella Chronicles. You will need to decide how many on-rails shooters you want though... with House of the Dead: Overkill and Dead Space Extraction already in the list, these two might not be worth grabbing at the same time.