I don't want much to do with anything similar to the Friend Safari. It's a cute idea - everyone gets something unique, and it promotes Nintendo's "connectivity" message, but nah. We don't need to deal with that again. Making sure that the other person signs on was irritating.
Instead, add in a Safari, with a time limit, rather than a step limit. Each time you friend someone you unlock another "Pokemon package". Like, you could originally start off with only three Pokemon, and each time you friend someone on the 3DS you'll unlock another three Pokemon. It'd be a cool idea, not as annoying as Friend Safari's and helps people connect with others. No random chances (as the three Pokemon would be set in stone, starting from weak mons). It'd be cool. :)