So if you enjoy burst and adapting to mage I would HIGHLY suggest Arcane first. Even at 120 in open world content. Arcane is actually very simple, but can be punishing if people don’t understand the mechanics of the class. It is likely the best dps spec in terms of pure output while leveling.
Get the heirloom caster trinket that restores mana after a kill (use two of those).
You can either play Arcane as you would at 120 (I.e. take Rule of Threes, RoP, Touch of the Magi; Do a Burn/Conserve) or what many people do for leveling:
ST: Take Amplification talent
Simply spam Arcane Missiles (using Arcane Power and Rune of Power for burst).
AoE: Charged Up + Rune of Power + Reverberation Talents
Charged Up for 4 Arcane Charges —> Rune of Power —> Arcane Power —> Arcane Barrage —> Spam Arcane Explosion until 4 Charges —> Arcane Barrage
AoE damage is primarily focused on Arcane Barrage at 4 Arcane Charges. Your goal is to get to 4 Charges as quickly as possible and dump those charges with barrage. Hence why you have 4 Charges and dump them with barrage at the start of burst (RoP + Arcane Power).
The trick with Arcane is just being mindful of your mana AFTER Evocation. However, at lower levels this shouldn’t matter all that much, just drink when you are low and the heirloom trinkets will help quite a bit.
The main reason I am saying go Arcane over Fire is that not only is it easier and better damage at lower levels, but I think that Fire will leave you feeling very dissatisfied. Fire damage output is heavily reliant right now on a few things at max level (to even feel like a complete spec): 3x Blaster Master Azerite Traits, Memory of Lucid Dreams R3 Essence, and the Mechagon Bracers.
If you didn’t enjoy Frost leveling, you’ll likely be in the same boat with Fire in a sense… the spec revolves around your Combustion which is a 2 minute cd. Damage output outside of it, without stacking mastery/haste will be lower in dungeons and feel pretty terrible. Not only that, but you will be fishing for Heating Up procs (extremely similar to the RNG aspect you didn’t like of Frost), with Arcane there is no RNG (both while leveling and at max level).
Lastly, Arcane plays virtually the same from 1-120 with very little variation (if you don’t do the Arcane Missiles for ST leveling, but many people do). Fire on the other hand can be much more complex and dynamic, but it is going to feel very lackluster before 120 and proper essences, Azerite traits, and gear—once you have all of that Fire will also have variations on how the spec plays. You will also hear people say not to even touch fire at max level without 3x Blaster Master and at least R1 Lucid Dreams (and people will hesitantly tell you that it’s not worth it even with 3x BM and LD without the Mech Bracers).
What I’m getting at is that if you are actually wanting to play the spec for its burst and for learning the spec, I do not believe that Fire will achieve those goals. It goes through some variation at max level (while Arcane doesn’t really), and Arcane is going to perform better in pretty much all aspects except potentially PVP before 120, and I say potentially because I think it is highly unlikely that the other two specs beat Arcane in lower level PVP, but I’m not 100% certain, I’m sure there is an outlier here and there. I mean if you search hard enough you will find people hard QQing about Arcane Mages deleting them in lower level BG’s using only Arcane Missiles and how it should be nerfed.