As I said up thread, I absolutely love AoOs and leaving them out would be a big hurdle for getting me interested.
However, I certainly recognize the "square counting" issue. My solution to that is to simply not allow it. It is easy to count to 4, 6, or 8. And it is even easy to just look at a board and see the options in the available radius. It is very common for a player to just say "I want to go here" or "Can I get to <there> and <the thing they want to do>?"
Typical answers are:
Sure, no problem
Yeah, but you are going to get attacked if you do
You can get to THERE safely or THERE with an attack
You can get to THERE and <do X> or get to there this turn and wait until next turn to <do X>.
If an attack is called for and the player takes the action, then they get attacked. They know not to waste time counting squares not only because no one enjoys that but also because they know they are getting attacked if they make the move. period.
It may be that there is some special square counting path that makes it mechanically possible. But if you can't glance at the grid and see it without counting, then your character can't find it in the 1/2 seconds of thinking they have while dodging the angry orcs.
Now there are certainly infrequent occasions when a player will go "wait, what about this path?" And I'm open to being swayed if it is quick and easy and reasonable. But reasonable is key and square counting is out of the question. Again, I can count to 8 (even using 1/2/1/2) pretty much with a glance, so that isn't an issue.
The only serious exception is crazy fast characters. When a character gets a move of like 12 or 16 for whatever reason, the bug turns into a feature. At this point the character is clearly supernatural is some way and it does make sense for their awareness to exceed that of other around them. And taking *A FEW SECONDS* to optimize a path just comes off as Jackie Chan bouncing off of walls and desks to take some crazy path and it ADDS to the fun. And, IME, the same people who will growl at the cleric for counting at all one round earlier will cheer the monk for doing his thing. On those events that it IS fun and IS part of the way the story should work: Go with it and enjoy.