This might be too late for you Steve, but we've really enjoyed these puzzles:
Infinity puzzlesIf you google "infinity puzzles" there are others out ther, but we've ordered from here with no problem. If the idea of an infinity puzzle doesn't excite you but you're willing to spend some coin on a "nice" puzzle, I would still recommend these guys.
EDIT: I was trying to attach this to a post I recall Steve posting where he was thinking of getting a good puzzle for someone for Christmas. Obviously this is the wrong thread....