Have you tried Famicom Detective Club 2 for SNES? It's not an overhead action game by any account (it's more of a visual novel), but it has an incredible story. No combat that I can remember, just some puzzles and some AWESOME translation work.
The DS is definitely the system we need to be looking into, but with region issues, firmware updating, the assorted flash cart options, (and having to import or pay heavily marked up prices) it's a bit daunting to bite the bullet on one.
I hear you there. A friend of mine got lucky (very, VERY lucky) and found an R4 card at a local pawnshop for 5-10 dollars. Maybe you might get lucky as well scoping out a couple pawnshops in your area as well?
Oh, if you or your loved one happen to use Android phones, there's a $5 DS emulator available that seems to be 10000% more stable than the one for PC. From watching my friend play it on his phone, it's simple and highly customizable, and makes games like The Sims 2 look like Gamecube games compared to the actual handheld.
Also, I know you said you can't do PSP, but if you happen to come across one (like say you check a pawnshop for an R4 card for DS, and happen to find an affordable PSP-Slim 2000 in good shape) putting custom firmware on it'll allow you and your loved one play damn near every older console up to PS1, you can play PSP isos (as well as rip them from your UMDs with the PSP itself with the right homebrew), and I've seen a plethora of homebrew games and older PC game ports for it as well.
Sorry if this is like a waterfall of text to go through haha. Hope you and your loved find some fun stuff to play!