I'm actually not happy that Fiora's dealing 40%~ of her damage as true damage but Riot gave their reasoning:
-
They said she was meant to duel everyone and in play-testing was bad against anyone tanky (i.e. armor stacking made her worthless).
-
They know from years of AD Carries and Critical Strike being a thing that if you make damage physical and then ramp up the numbers to be able to kill armor stacking tanks then squishy champs get literally one-shot.
-
They want Fiora to be a skillful duelist, preferably with a hit-and-run lane pattern, and NOT an assassin that can just one-shot squishies with a ton of physical damage (i.e. if they were to go with your first suggestion they already know that we will play her as just an assassin and that isn't how they want her to play).
-
Flat true damage gets through armor but is much, much better against squishies since tanks will just get health and not care.
-
Funny thing about % Max HP True Damage. It's fair. The numbers don't matter. 12% means 12% whether your health is 500 or 5000. Would you rather Fiora deal 1000+ physical damage just to actually hurt the armor stackers she's intended to fight? Of would you rather she deals only 200+ damage to everyone equally even if it means tanks have to eat some damage they can't itemize against?
-
Making the % Max HP True Damage scaling with AD did a very important thing: it makes building AD glass cannon the optimal path, giving her the weakness of being squishy, rather than encouraging her to build tank (which Riot said they saw in play-testing).
It's like in Final Fantasy II (the actual one, not the one that was really FF IV) where they had monster attacks that hit for 1/16 of your max HP. People said it punished them for trying to get more HP since it did more damage the higher their HP got. But here's the thing: it ALWAYS killed in 16 hits. Getting more HP and getting better armor was still awesome at surviving everything else that was being thrown at you - it was just those specific monsters that could actually hurt you and they would kill you in 16 hits no matter if you had 999 HP or 9999 HP.
Personally, I would rather Fiora did not do so much of her damage as true damage. As a melee carry she needs to do tons of damage to EVER be worth picking, but I'd be down for more being physical. But she WILL need some more physical damage somewhere if she loses true damage. Higher base AD, higher base damage or scaling on her Q or E - your pick.