Any theories as to why AOD slows down with the map fewer provinces.
If there are no other DB file changes (or issues introduced by the map change that could result in more frequent or sub-optimal calculation of various game mechanics), then I would suggest to check the number of land provinces connections (these matter more than the actual number of provinces as more connections mean more possible routes from province A to province B). Too many connections are also bad for game-play experience (harder for the player and for the AI). For DH map we tried to have number of connections for land provinces to be less than 5-6 and this solved a lot of issues we had in the pre-release version of DH.