I picked up the Vienna Gambit a year ago and ran into the same quandary over 2. ... Nc6, I generally agree with your assessment of each candidate move, and I don't see that you have much real choice apart from those four. Taking into account that your preferred line is the Vienna Gambit, and that you'd like to be able to deal with alternatives to 2. ... Nf6 in a similar spirit:
- Nf3 definitely isn't what you want! If you were comfortable/happy with 3. Nf3, you'd play 2. Nf3 instead of the Vienna.
- Bc4 is a pity. Before switching to the Vienna Gambit, I was originally drawn to the 3. Bc4 Vienna because of the fairly reliable prospect of getting 5. f4 without gambitting the pawn, but indeed, Black can and should spoil your fun by trading off your bishop with Na5 as soon as you've played d3. The resulting position is playable, but as with the Four Knights, generally not much fun for the sort of player who'd opt for the Vienna to begin with. In practice, a lot of players unfamiliar with the Vienna will instead give you 3. ... Bc5 4. Qg4!, so this could be a workable choice in club-level blitz, but "hope chess" should never be the basis of a repertoire decision.
- g3 is a much slower and less forceful way to achieve f2-f4 and results in positions of a very different character from developing the Bf1 to c4 or b5. Once again, playable, but not in the spirit of the Vienna Gambit.
My recommendation is to take a closer look at 1. e4 e5 2. Nc3 Nc6 3. f4. Granted that it's a transposition to the King's Gambit where Black can take the pawn freely without fear of 4. e5 ideas found in the Vienna Gambit, but I think you'll find that the character is about as close as you're going to get to the Vienna Gambit without risking the boring Na5 lines of 3. Bc4, and in chess we don't have the luxury of always getting exactly the flavor of game we'd like. If your concern is that it's riskier than you prefer, consider the following:
- Going back to the Vienna Gambit proper, remember that Black can accept the gambit and walk into 4. e5. It's a bad decision, but it's not an instant loss, it's hardly risk-free for White, and it will require some technique from you to fully take advantage of Black's misstep. By playing the Vienna Gambit, you sign on to occasionally play the crazy King's Gambit-ish positions that result from Black accepting the gambit. In this sense the 2. ... Nc6 3. f4 lines are similar in character to the Vienna Gambit.
- With Nc3 and Nc6 having been played, a quick d7-d5 is ruled out. You're playing a King's Gambit where Black doesn't have access to the Falkbeer Countergambit 2. ... d5 or the Abbazia Defense 2. ... exf4 3. Nf3 d5. Black has fewer credible replies, and can't really decline the gambit except in ways that permit you to keep your pawn on f4 and transpose into 3. Bc4 Vienna lines where Black hasn't played Na5, which should be pleasant enough for a Vienna Gambit player.
- If Black does accept the gambit, presumably you're going to respond 4. Nf3; if you're happy with Vienna Gambit levels of risk but not King's Gambit levels of risk, then allowing 4. ... Qh5+ and having to move your king is probably not your cup of tea. So now we're looking at the 3. Nf3 King's Gambit proper, except the presence of Nc3 and Nc6 limits Black's options and slightly modifies the character of the remaining choices, a small plus to the Vienna player in terms of familiarity that should decrease the risk. You're also one move closer to being able to castle long, generally desirable both for safety and for achieving positions closer to what you would have gotten out of the Vienna Gambit main lines from 3. ... d5 4. fxe5 Nxe4. In many cases you have a decent prospect to fight for d2-d4 and Bxf4.
There are two main issues for you to consider in the lines after 1. e4 e5 2. Nc3 Nc6 3. f4 exf4 4. Nf3. If you can reconcile these with your tastes and aptitudes, then I think 3. f4 should be absolutely fine for you.
- Just as in the King's Gambit, even if you opt for Nf3, Black may play Be7 and uncommon Bh4+ ideas that will require you to either move your king or (if you played Bc4 in advance) castle short in a tricky position where you have neither f nor g pawns and Black is bearing down on you. The database stats are encouraging either way, but you will need to know what you're doing and you will need to be comfortable playing in some really madcap positions.
- Nc3 and Nc6 aren't solely an improvement for White; the presence of Nc6 means that if Black holds the f4 pawn with 4. ... g5 (by far the most popular choice), and then pushes 5. ... g4 (popular if you play 5. d4 or 5. Bc4, all but guaranteed if you play 5. h4), now you can't simply play Ne5 and preserve some degree of sanity. With Black's Nc6 preventing you from escaping to e5, you basically need to be prepared to sack the knight, whether that's 5. d4 g4 6. Bc4 gxf3 (or Bc4 first and then d4) in the style of the Muzio Gambit, or 5. h4 g4 6. Ng5 h6 7. Nxf7. Just about the only alternative to sacking the knight (aside from retreating it...) is 4. ... g5 5. d4 g4 6. Ne5 Nxe5 7. dxe5 Qh4+, which to me looks considerably weaker. Good news, both knight sacks are playable if you know what you're doing. Bad news, most likely neither of them is perfectly to your taste if you opted for the Vienna Gambit over the King's Gambit. EDIT: A major alternative to sacking the knight in the 4. ... g5 lines: 5. g3, establishing a refuge for the knight on h4 and pretty likely transposing to the Quaade Gambit (1. e4 e5 2. f4 exf4 3. Nf3 Nf6 4. Nc3) with good play from both sides. The transposition is rarely played, but I can't see a single thing wrong with it.
In the end, no opening is going to give us exactly what we want 100% of the time. 1. e4 players get to pick their poison between the Ruy (the Berlin stifles the greatest attacking players), the Italian (3. ... Bc5 can be a slog, unless you like the Evans Gambit), the Scotch (3. ... Bc5 again...), various gambits of the d4 pawn, the King's Gambit with Black's numerous strong retorts and White's razor-thin margin for error, and the Vienna with the potential drawbacks you've noted in each major variation. The other possible first moves for White all have their own equivalent issues. Take your pick, either based on which troublesome lines you're most likely to meet, or based on which troublesome lines you would most prefer to never meet. I've tried most everything listed here and found that my personal preference is the Vienna Gambit, with 3. f4 in the case of 2. ... Nc6, and while it's certainly not a choice without drawbacks, you don't have any choices that are wholly without drawbacks. My advice is to examine the 2. ... Nc6 3. f4 lines a little more closely and decide whether the most thematically problematic line (1. e4 e5 2. Nc3 Nc6 3. f4 exf4 4. Nf3 g5) is preferable to your grievances with the alternative third moves.
Personally I've found that if I look hard enough, most any opening has at least one line against it that's both strong and not to my liking thematically. I've grown to enjoy chess more by spending less time dwelling on those possibilities, and more time thinking about the lines where I do still have control over whether the game goes in a direction I like. Can you guess how many times I saw the nasty Na5 lines before I abandoned the 3. Bc4 Vienna? Zero. I quit playing that line because I was afraid someone might play it. That's no way to live. Play the way you want to play, and make revisions later if it doesn't work out, but do play something, and let the practical results guide you rather than phantom critical lines.