Tetris DS or Planet Puzzle League are two of the most pure, ideal puzzle games… but they’re sadly rare these days.
If you liked EBA, you may love Rhythm Heaven. It’s a great Warioware-style collection, but with addictive music and rhythm games that each tell their own little story, tho not as deep as EBA. Lots to play and unlock.
Picross is great, too - uses the same logic as Sudoku, but more picture-based.
If you don’t mind slightly rigid puzzles, the Ace Attorney games may be worth a play through. They have decent stories and lots of really fun moments of revelation and redemption in the play-courtroom.
And since I love RPGs, I have to recommend some of the best from way back when: Chrono Trigger and Final Fantasy IV. Either can keep you occupied for weeks and weeks. If you’re looking for more mold-breaking offerings, try SMT: Devil Survivor or The World Ends With You.
Also: keep an eye out for Scribblenauts in the next couple of months. This will be a sleeper hit.
“Henry Hatsworth and the Puzzling Adventure” is a fantastic puzzle/platform hybrid. You switch between both modes throughout the level. Both of them are relatively simple on their own, but they interact with each other beautifully (your performance in the puzzle affects your platform game and vice versa).
It starts of very easy and ends up being a pretty darn good challenge, also it’s $20 now.
As far as RPG’s go, “Dragon Quest V” is just fantastic. It is a remake of the classic game, your mileage may vary according to how much you like Dragon Quest (a pretty old school system). But it’s just top notch for what it is.
It might not be your thing, but Zelda: The Twilight Princess was f-ing cool.
Though, admittedly, I feel that way about all Zelda games.
Oh, and I agree with you about Professor Layton. Can’t wait for the next game to come out.
I enjoyed Mystery Case Files: MillionHeir far more than I thought I was going to. The main activity is finding specific items in very cluttered scenes against a clock, but there are other puzzles along the way too.