I got Legend of Zelda: Oracle of Ages and Seasons on my 3DS XL, and these are amazingly charming little games that have aged incredibly well. I really wish there were more quality games for the 3DS Virtual console.
It might not be on the 3DS, but go find Link's Awakening- it was built on the same engine as Ages and Seasons, but it's just so much more. T'was a gem from the Gameboy era and easily playable today if you have the means.
Get link's awakening DX instead. It's the remake with color and a bonus dungeon. This site is about the best you are gonna get, but you will need to register on the forums if you want to save your games. Though, I feel it appropriate to warn you that the forums are a more conservative than the bay12 forums.
I spent a minute looking, and Link's Awakening DX is available in the Nintendo Eshop for six bucks. Also, there's the original Legend of Zelda and Zelda II from the NES era, though those don't look as appetizing.
If my money bladder didn't hurt so much from just thinking about shoveling out 40$, I'd buy Ocarina of Time 3D, a remake that's now handheld. I wouldn't consider it a bad purchase though, it looks extremely appealing since I never finished the N64 version, mostly because ReDeads scared the shit out of me as a child. However, now that I'm an adult, I can now experience the awful, nightmare inducing screeching and molesty grope attacks of those monsters IN 3D!
It's not out yet, but there's a Zelda game in the works Called "A Link Between Worlds" that's cell-shaded 3d like in Wind Waker, set in an isometric viewpoint and control scheme like Link to the Past, that's going to be a 3DS exclusive. Even if it's a bit heavy on the 3D feature, just judging from the trailer, it looks pretty awesome.