...try Nurikabe. I know on link has already made the rounds, but I found another one with a bunch more puzzles. This is via Google Translator, as the initial site is not in English. So here's some Nurikabe for y'all.
For those not familiar with the puzzle: you're given a rectangular grid of arbitrary dimensio, splattered with a few numbers. The goal is to identify which squares are white and which are black. All the black squares must form one contiguous region. There may be no 2x2 block (or, of course, larger- which would contain the 2x2) of black piece. Finally, white squares form contiguous regions called "islands", separated with black squares and board edges. Each island contains exactly one numbered square, each numbered square is white, and each island contains exactly as many white squares as its numbered square says.
This can be a nontrivial puzzle.
Try puzzle.jp for another site and all that. I ordered a few puzzle books from Nikoli, a company that makes such puzzles. Totally worth my money.
Seems a lot more dynamic than Sudoku. At least the way I solve it, which is 'try things out, find out where it goes wrong, figure out how to fix it'. Seems to be a nice strategy so far.