I seem to be an odd man out in this thread as I thought AC3 was excellent and on par with AC2 in its storytelling. Connor's struggle was well done in that he isn't really on anyone's side, just fighting to protect his tribe and keep them safe. The Templars were much better handled in this game than previous ones. For the first time since AC1 I could actually sympathize with them and their motives and felt sort of bad for killing them. The Templars of the Ezio trilogy seemed more like power hungry stereotypical villains.
I liked the openness of the frontier as having a sandbox area was something I missed in ACR. I thought the naval missions would be horrible but they were one of the best aspects of the game. I know there were complaints about the amount of cutscenes but some of them were truly exceptional, such as the last cut scene with Connor and Lee. Overall an amazing game.