I recommend TWEWY as well, the story will hook you up right from the start. Other than that, go for Nostalgia or Glory of Heracles, both are greatly praised and are on my "to play" list.
If you'd like another adventure, try Another Code. Although it is rather short, it was made by the same company that did Hotel Dusk, and HD contains references to this game.
And if you have played Kingdom Hearts for PS2, I'd recommend Kingdom Hearts 358/2, it's superb. If you haven't played the other games, it'll still be really entertaining, but you'll miss out on some things. (the pcsx 2 beta 1888 (Playstation 2 emulator) will play both Kingdom Hearts 1 and 2 perfectly, if you have some time check them out!).
But personally, I think the best game ever both story-wise and battle system-wise is the Golden Sun for GBA, so if you have a slot-2 flashcard (or now the DSTWO), do try them out ("them", because the game is technically split into two, so you have Golden Sun and its continuation in Golden Sun: The Lost Age). And of course, FF8 (but this one's only on the Playstation or PC, not on the DS. Go for the PC version.).