Considering you're playing with friends, I highly suggest Medivh, and obviously some one go healer and if more friends, one goes tank, or at least carry a shield and a 1h with ya, since early on thats enough.
Outland will be fast leveling and quick to end game, which may be appealing, but it will have a cash shop, medivh is said to not have such feature.
I don't believe even Outland will be "p2w", as they will probably sell current tier gear at best never gear that can't be obtained ingame, but still, some find that too much to swallow.
The "drawback" of medivh is slower leveling, but I personally enjoy the leveling part as well, and with friends it can only be better, as at all levels you'll all probably be on your best gear since you can constantly do dungeons (and dungeon quests).
I'd stick with Medivh if you plan on long fun journey, if you want a quick refresh of TBC and then move on, then Outland might be better, up to you what you want.