Oh, you'd be surprised about StreetPass. It's not about live multiplayer gaming, since you're picking up others' Miis when you walk by them, and "using" them in the games, not really interacting with them. Really it's a bunch of single-player games, where you just need to run into other people with a 3DS to progress with.
For starters, you'd be getting puzzle pieces you need to complete Nintendo-themed puzzles (you get copies of whatever puzzle pieces they have, and they would get copies of whatever puzzle pieces you have), or using them in Find Mii (and Find Mii II), an RPGish game where you use collected Miis to fight monsters, and the colour that they're wearing determines what magic spell they have on hand. At least try those free/included things out before you decide if you want to buy any of the other StreetPass games, of which the current four others are really quite neat and varied:
-Mii Force: a spaceship shooter where each person you StreetPass provides a different weapon depending on their colour
-Flower Town: a game about growing flowers where you pollinate with other people's flowers
-Warrior's Way: a strategy game about conquering the world using rock-paper-scissors to defeat others' armies
-Monster Manor: a puzzle/RPG where the colour of StreetPassed Miis allow you construct rooms with that colour, and bigger rooms of the same colour get you treasures
I'm also not a social gamer when it comes to handhelds, for whatever reason, but I love all the StreetPass games - if you carry your 3DS around all the time like I do, you're bound to get some each day, and it's a nice twice-to-thrice daily diversion.
As for the games you mentioned, I loved Super Mario 3D Land (longer yet easier than expected), any Shantae game is good, and I enjoyed Ocarina Of Time (yet again, and the 3D effect is really nice in that). I must say New Super Mario Bros. 2 was okay, but I didn't enjoy it anywhere near as much as Super Mario 3D Land or even the other New Super Mario Bros. games and I never felt like going back to get the 1,000,000 Coins goal. Of course I'm looking forward to The Legend Of Zelda: A Link Between Worlds which comes out tomorrow, but currently my 3DS time is devoted to StreetPass Mii Plaza (I'm serious), and Pokémon Y (not sure how interested you would be if this is really your first handheld, but it does feel friendlier to newcomers to the series).