The nice thing about these... particularly Pokemon... is that they really do work well for all ages. Heck, you should see the Pokemon fanbase; you'd be surprised just how much of it is adult geeks instead of kids, haha. There's major tournaments and such for the actual video games and everything (and for the card game). I've always really enjoyed the Pokemon games myself; Yu-gi-oh, I had that card game as a kid, but that was a long while ago and my memory of it is a bit warped.
For pretty much anyone, kid or adult, if I had to pick one of the two card games, I'd say Pokemon is probably the easier of the two to learn yet with plenty of overall depth to it (whereas I remember that Yugioh could be a bit convoluted and strange at times, and was about as balanced as a drunken monkey on a trampoline). Now, from what I hear... I havent actually tried this myself, though I might... the online game client (as yes, the card game has an online version) is the easiest way to learn the game, having a full tutorial and all. Though, I'm thinking that the starter decks probably have a pretty well made rulebook or whatever too. It being what it is, they've probably made it pretty easy to understand, and unless the rules changed since I last played this, they're easy enough to grasp when getting the hang of it. As with any TCG, the challenging stuff all comes later on.
And they have this product too: http://www.pokemon.com/us/pokemon-tcg/p ... ainer-kit/
That can be found at most stores that carry the game, I've seen this a number of times, and similar things like it. Comes with pre-constructed decks and everything needed to learn. So that might be your best option right there!
Hopefully that helps a bit... any questions, just ask!