I think one of the strengths of this game is that everything is unlocked right from the get-go. You don't need to spend hours and hours grinding to unlock the "real game."
That said, would it work if you had to play the tutorial for each class to unlock it? Then, at least, you're actually playing a little in-game before your first match. The tutorials are (very) short, and while basic they would acquaint people with the mechanics of each class. Or perhaps offer some other reward for doing them; a unique hat or something for each class if you do its tutorial. (always in favor of more hats) You'd just have to change the main menu UI to draw people to it.