Of course you can always try getting your feet wet with Cube-like settings (and it can be incredibly fun), but trying to crunch constructed decks from a limited pool is something I wouldn't necessarily recommend, as it's all but guaranteed to have any balanced results. In general, card-by-card construction is something I'm skeptical about for beginners, balancing and pricyness being not even the main reason:
At least to me, customizing your deck to suit your personal playstyle is a main factor in what makes MTG so intriguing; simply baking up a set of cookie-cut decks might make for consistent (albeit not necessarily fair) matchups, but pretty much removes that aspect entirely.
On my cap, the best steppingstone regardless of what format you aim for would be the preconstructed intro packs or duel decks - I'd recommend the latter, as they typically pack more punch for their money, and are specifically built to go up against another. This is where you come in - get a hold of the decklists for the packs currently available, talk to your friends about which aspects they'd like to see more of in your games, and which pack would best meet that.
Each of these give each player a playable base to learn the curves with, and to tweak and improve upon for themselves by adding or removing certain cards - which is again where you, as the one with the card-pool and experience, can help them out, or they themselves might want to expand their repertoire.
Once everyone has a deck to play with, all that's needed is
- A Setup where Everyone gets to play
Two-Headed Giant being something you're already familiar with, here's a multiplayer variant for 5+ players, perfectly fit for quick lunch-time games, a format dubbed "Bad Neighbour" by our local playgroup. It's a setup that can be played with any number of players, really, but it's best suited for groups of 5. Here's how it looks like:
The player to the left and the player to the right (your "neighbours") are your opponents. Those two players (and planeswalkers they control) are the only people you can attack. It is your goal to get rid of these two by whatever means.
The two players on the other side of the table are your allies. You cannot attack them, and they can't be targeted or affected by any effect aiming for an opponent (example).
The first player to have both of their neighbours eliminated is the winner.
The big advantage this has over free-for-all is that "Let's all kill Jeff first, he has the strongest deck!" kind of scenarios aren't possible, and games are typically shorter, making them less of a pain for those who fail out early. It's a rather diverse experience too, since simply switching seats makes for a whole set of new matchups. It also offers a less cramped gameflow than the classic 5-star, as you won't have the two players trying to bring you down consecutively take turns, but rather get to to your own thing between the two, allowing everyone to play a lot more offensively.
In summary, it's pretty much the best setup I know of for when there's a lot of players, but only little time.