Yeah, hate to say it but 4MPS is pretty bad. I get over 10x that using a wired connection
Are you using a wireless connection? If so you might want to invest in an Ethernet cable. If you already have one then sorry, time for a new ISP :P
I would also like to point out that with my connection i only get an Orange NAT on AC Multiplayer. It is just as much Ubisoft's fault as it is yours trust me.
I'm ecstatic right now since I've figured out how to fix NAT issues in not just AC,but all games. First obviously make sure you have UPnP enabled, or your ports forwarded (I use both,hasnt caused problems) Inbound and outbound firewall rules are set for both multiplayer and singleplayer. now those alone didn't fix my problem. I even tried disabling my router firewall. The fix I found was:
-Once that's downloaded,run as administrator and set the connection speed to the spped your ISP has provided for you, check modify all network adapters, check the "Optimal" setting, click apply changes, reboot.
-Go to pingtest.net and check out your ping. Before I did the above steps I was at a 64/mbs network speed which isnt bad at all, but applying the changes reduced my ping by 40/mbs. I'm at 23/mbs after the changes.
-Go to AC multiplayer and check your NAT Status.
-Note that for the above to work, it is recommended that you already have good bandwidth.
enable UPNP in your router's settings
forward port 3074 UDP in your router's settings (this is the only port game actually uses for P2P, the only one it forwards with UPNP and the only one used to test your NAT in game).
If this does not help try disabling firewall. If even this isnt enough its time to change your ISP
I wish that were the truth but I've already confirmed that I have port 3074 open in a port checking program. Perhaps having that port open can get you to moderate from strict but for me, it will not be open.