I believe that Savage Worlds meets your requirements
Easy to balance, no significant "tiers" of career paths
Savage Worlds is classless, and allows you a great deal of flexibility in the way you build your character. Although there are Professional Edges, these are very specialist, and do not lead to the types of career paths you get in some other systems.
This tends to make the system relatively straightforward to balance, and as long as you are aware of the strengths of individual characters then it is simple to design sets of encounters that spotlight where necessary without letting one type of skill set dominate.
Fast rules in session (at least once players know special rules they want to use)
The Savage Worlds ruleset is relatively simple, with a common dice roll mechanic that is used for the vast majority of situations. For a typical fantasy genre game, individual magical powers might have some added complexity, but only to a certain extent.
Variable character complication. It's OK if wizard's spells get complicated, they are slow to learn and may be complicated to cast. It's not OK for simple warriors to be complicated, if someone wants to play hit'n'smash, let him
Characters that cover most of the common niches in a typical fantasy party can be built with a desired level of complexity. This is done by carefully selecting their Edges, which are typically the aspects of the character that allow them to perform manoeuvres/tricks that are special cases with their own tweaks to the rules.
No limits without justification
I am not aware of any unjustified limits in the system. Magic users are typically limited by having a set number of power points to cast their spells with that recharge over a set period of time. Strength limits the carrying capacity of all characters, acting as something of a balance for non-magical characters as it can significantly reduce the amount of armour and number of weapons that can be feasibly carried.
Easy for DM to scale encounters for players without too much math and planning ahead
NPC design is simple, and the core rulebook provides a rough mechanism for helping to ensure encounter balance. However, this will vary depending on the exact capabilities of a particular party.
Dice based chances over narration based ones. Less dices the better, but that's not critical
There are no systems that reward players with greater chance of success based on the quality of their narration. However, the benny mechanic, similar to things like fate points includes suggestions for how bennies could be earned, and one of these is often for providing a particularly vivid description of a character action. Having said that though, its easy to ignore and will not affect the balance of the game if you are consistent with all players.
Rules stiff enough to prevent advantage of more imaginative payers, or players who simply happen to have more time to prepare. Time and imagination should contribute to fluff etc, not to power
As previously commented, 99% of the rules are based around a common dice mechanic that provides the GM with a framework to adjudicate on edge cases that imaginative players might come up with. This helps to ensure consistency and prevents such cases from offering unfair advantages.
Readily available high-fantasy rules (not necessarily whole setting, just rules would suffice), like magic and typical monsters, so we don't need to invent all of it from scratch. We don't mind filling some gaps, but we simply will not write a substantial part of the game
The core rules have everything you need to get started with a fantasy genre game. In addition, there are a number of other products that would be well worth your attention. In particular, The Fantasy Companion extends the basic rules with a large number of additions specific to the fantasy genre, including new Edges and Hindrances, genre specific equipment and magic items, and a large menagerie of creatures.
There are a number of Savage Worlds settings that sit within the fantasy genre including Hellfrost, Beasts and Barbarians and Shaintar. I have personal experience with Hellfrost, which is one of my favourite settings in any system, but not with the others.
Classless and levelless
Character advances are based on the amount of experience points earned, which themselves are not tied to killing monsters. Every 5XP gives you an advance, which can be spent in a number of ways (increasing skills, attributes, buying Edges).
Characters also have Ranks, which limit access to certain Edges. For example, Novice is from 0-15xp, Seasoned from 20-35. This mechanic helps prevent access to the more powerful Edges too early in the game.
Various aspects of what we know as classes should not be tied to each other. Like "You can't be better at picking pockets unless you learn to backstab people better as well" - why? What if someone does not want to backstab, at all? That's why I don't like levels
Granularity is at the skill and Edge level. Skills are completely independent, but are linked to the basic character attributes. This means that a character with high Agility will find it cheaper to increase skills linked to Agility. Edges often have prerequisites in the form of minimum levels of certain skills, but in my opinion these make sense. For example, the Edge 'Martial Artist' requires a minimum level in the Fighting skill, representing the fact that to perform the feats the Edge gives you, your character would have to have a certain proficiency in basic melee combat.
3 to 6 players, usually
The system scales well with player number, and I've been involved in successful games ranging from 1 all the way up to 8 players. I'm also aware of GMs that have run with tables of 10-12 players, although that is outside of my personal comfort zone as a GM.
Campaigns we play vary from 3-session ones to half a year ones
Campaign length depends solely on the desire of the GM and players at the table
Mix of old and new players
Savage Worlds is a relatively easy system to pick up and play
Getting a quick look at the system without having to spend anything
As an additional bonus, there are test drive rules and a number of one sheet adventures that cover a wide variety of genres, all of which are freely available to download and try out.