Fortunately, there are some things you can do to mitigate the problem, regardless of whether you're an AMD or Nvidia user.
Assassin's Creed IV's V-Sync support is oddly implemented. First, the game's engine is capped at 63 FPS, period, no matter what. Turning V-Sync off has absolutely no impact on the maximum frame rate, provided your GPU can reach 63 FPS. Turning V-Sync off will cause tearing and allow the frame rate to move dynamically between 63 and 30 FPS, but it won't allow for anything higher than that.
See the jump between 60 FPS and 30 FPS at erratic intervals? That's the behavior we want to eliminate.
Since the game engine can't exceed 63 FPS, you might think that there's no benefit to a higher refresh rate. This is untrue. The way V-Sync is designed to work is this. The game will try to run at the refresh rate of the monitor (usually 60Hz). If it can't, it'll fall back to half speed, or 30 FPS. If it can't maintain 30 FPS, it will fall to 20 FPS.
Unlike most games, which allow the end-user to set the refresh rate directly from an in-game menu, Assassin's Creed IV uses the desktop's refresh rate. If you own a high-end monitor that's capable of a 100Hz refresh rate or more, setting that rate on the desktop will ensure a much better experience. If your monitor can handle a 120Hz refresh rate, for example, that means V-Sync will attempt to hold to 60 FPS. If it can't maintain 60FPS, it will fall back to 40 frames per second. Not only is the gap between 60 and 40 FPS less jarring to the eye, Sustained 40 FPS is far smoother than sustained 30 FPS.
Solution #1 is to increase your monitor's V-Sync setting. If you do, you get a pattern like the above, where you can see performance is split between 44 and 60 FPS, with a few isolated drops below that. But the truth is, there are only a handful of 1080p displays that push above 60Hz. If you own one, great. If you don't, we need a better solution.
Enable Adaptive V-Sync (Nvidia)
Nvidia's Adaptive V-Sync is one way to solve this problem. Adaptive V-Sync works by disabling V-Sync on the fly when the frame rate falls below 60 FPS, and re-enabling it when the frame rate is back at that point. The advantage to Adaptive V-Sync in Assassin's Creed IV over just running with V-Sync off is that Adaptive V-Sync helps reduce the screen tearing that otherwise plagues the game.
To enable Adaptive V-Sync: Right-click on your desktop, choose "Nvidia Control Panel," click on "Manage 3D Settings," and then select "Adaptive" from the Vertical sync options, as shown below.
The impact on the game's frame rate and overall smoothness is significant. The image below shows Assassin Creed IV's performance in 192x1080 with maximum details and FXAA enabled running on a GTX 770. V-Sync is enabled on the left and Adaptive V-Sync is enabled on the right.
Download Radeon Pro (AMD)
AMD doesn't have an equivalent to Adaptive V-sync supported in its drivers, but there's a third-party utility that can provide the function: Radeon Pro. The latest beta version can be downloaded from the website (this last version adds support for the R9 family of cards). The first thing you have to do to use Radeon Pro is create a profile for the game you want to use. Left click on the green plus, navigate to the Assassin's Creed IV directory (typically C:\Program Files (x86)\Ubisoft\Ubisoft Game Launcher\games\Assassin's Creed IV Black Flag\ and choose the "AC4BFSP.exe" file as a target.
Then, click on the "Tweaks" tab, find the V-sync setting at the top, and choose "Dynamic" as shown below.
With Radeon Pro set for Dynamic quality, the R9 290X's performance profile changes dramatically.
Note that in this case, the reason the R9 290X is pushing a nearly perfect line while the GTX 770 shows variation is due to relative performance -- the R9 290X is the much better card and I don't have a GTX 780 to put up an apples-to-apples comparison. The bigger point is that the problem is solved, for both cards.
Smoother frame rates lead to better experiences
This solution won't magically make the game run faster for everyone -- you still may need to turn detail levels down to hit your preferred frame rate -- but if the jerky behavior has been annoying you, it should improve the game.
Special thanks to both Nvidia and AMD, where teams on both sides helped me track down this issue