Pathfinder's box set is, in my opinion, one of the nicest self-contained game presentations I've ever seen. I'd recommend it without a second doubt; it has folding maps and cardboard character printouts with bases that immediately offer a low-budget battle map, and it has enough content to give players a bunch of fun. Plus, Pathfinder's SRD is pretty massive, so there's no paucity of new content for creative play, and there are a ton of adventures out for it (as there are for pretty much anything). I also found learning Pathfinder much more simple than learning any of the other modern games out there, and it has perhaps the most minor-friendly content among them.
All the D6 games are available free as PDF's over on DriveThruRPG, if the beginner players are tech-savvy. That doesn't make it much of a gift, but you can also get the D6 books for ~$20 or so on Amazon, depending on which you want, and the D6 system's pretty easy.
1km1kt is a site for free game development and such. You can find a variety of games on here that have a ton of different genres and levels of complexity, including "pocketmod" games that can fit happily on a single page. Ask around on the forums, since 1km1kt is at least a decade old and some great gems are buried in its archive, including but not limited to one of the best superhero games I've ever played (back in high school, which probably lets people know how old/young I am).
This is, of course, far from an exclusive list, but when I introduce players to games this is typically my order of doing so (unless I feel like dropping them in hard on my Shadowrun campaign, which is not a easy game).