The current appoval system isn't helped by the fact that there is something wonky going on with Approval Relics. I haven't reached 100 planets in my brand new Beta 6 game, but when I was on 5.3, my approval started to tank once I hit 100 planets, even though I had more than enough Relics to cover my size penalty. Yes, I already sent in a ticket on it.
Beyond that though, I do think the empire size penalty should be somewhat dependant on map size. Or rather, number of planets that can be colonized (sorta like how the tech rate is dependant on that currently).
One good thing is that there ARE several new sources of percentage based approval in B6. One of the political parties gives 20%. One of the benevolent traits has been changed so that all starbases give a pecentage based boost within its ApE (it's a level 5 trait so it's gonna be a while for folks to get it unless it is beelined to). A couple of the other techs that were unlocked also are percentage based.
Still, even with all of that and a fully working approval relic system, it might not be enough. I am somewhat doubtful that I can get 1500% bonus to approval on all planets even with huge amounts of cheesing.