Convert both images to grayscale.
Compare the contrast of each in the areas where you told the camera to focus. Which has more contrast? Compare the contrast of each in the areas surrounding what you were attempting to focus. Which has more contrast?
The camera will only work with what you, as the photographer, give it to work with.
Autofocus systems in cameras work based on contrast. If there's very little contrast where you are telling the camera to focus it's not going to perform well, if it performs at all.
Pretty much every camera user manual I've ever looked at that was for a camera with autofocus capability has a section that describes when the camera may have trouble focusing. Your D3300 Reference Manual includes it on page 76.
The image of the seal demonstrates some of at least all three of the right hand column of the list.
Most 70-300mm lenses (you haven't told us exactly what 70-300mm lens you were using, Nikon has produced more than one variant in that focal length) have a maximum aperture of f/5.6 at 300mm. This means that even though you are shooting at f/5.6, you're also shooting at the lens' widest aperture at 300mm. Almost all consumer grade lenses are sharper stopped down a stop or two than they are wide open.
The angle of view with a 300mm lens on an APS-C camera makes it look like a 450mm lens on a 35mm camera. It also simulates the DoF of a 450mm lens on a 35mm camera due to the additional enlargement needed to display the APS-C image at the same size as a 35mm image. Most depth of field charts assume a standard display size of 8x10" viewed from a distance of 12 inches. If you enlarge an image to view it larger than that, you also enlarge the blur in the image which has the side effect of reducing the perceived DoF.
Which leads us directly to: f/5.6 is right at the edge of the smallest wide open aperture that the Nikon D3300's AF system is rated to function. For why the lens' maximum aperture affects AF performance, please see Why does the autofocus capability depend on the aperture rather than the amount of light available?
When faced with a lack of enough contrast to focus the lens, most cameras will expand the area until they find some kind of contrast somewhere near the designated AF point and then they'll focus in that. Or they'll start "hunting" by moving the lens' focus in and out until some detectable contrast is found at the designated AF point(s). Or they'll give up and take the picture anyway, or refuse to take the picture at all.
It looks to my eye like the camera was focused at a shorter distance than anything in the frame when the image was captured. The way the specular highlights in the lower left part look might indicate VR was active during the exposure, but it is hard to say conclusively.
There's also the possibility that you accidentally turned off AF or that your lens requires an in-body AF motor that the D3300 lacks to power the lens you were using. With regard to the bird being in-focus if AF was non-functional: Hey, even a blind squirrel finds a nut sometimes and even a broken clock is right twice a day!
Beyond that, there are a couple of other things mentioned in the question that should probably be addressed.
Clearly my shutter speed is fast enough to eliminate jitter/camera
movement and my DOF seems appropriate.
Using 1/500 second with an APS-C 1.5X crop body at 300mm barely meets the 1/focal length 'rule of thumb'. The angle of view with a 300mm lens on the D3300 is the same as the angle of view of a 450mm lens on a 35mm camera. The 1/focal length 'rule of thumb' is based on the assumption that good camera stabilization techniques are being employed. There's plenty of room for 1/500 to be too slow for a 300mm lens on a D3300.
That doesn't appear to be the case with your example image, but you probably shouldn't summarily dismiss it out of hand.
VR on
VR certainly helps with camera movement, but it isn't perfect and there's no substitute for using proper camera stabilization techniques. Even a fairly mediocre tripod, when used properly, will beat the best performing VR lens on the market. VR movement has limits and if the VR unit is already at maximum deflection and the camera continues to move in the same direction it can do nothing more to move the VR unit in the needed direction. Keep in mind that when a VR element moves it is an intentional misalignment of the lens elements in the VR unit with respect to the other elements in the lens and that can affect image quality. In general the benefit of reducing camera shake outweighs the penalty, but not always. A small percentage of shots taken using VR can be very blurry. I've always attributed this to the shutter opening at the same moment the VR unit is recentering. But that should only affect a very few random images, not every single one.
There are several very detailed questions and answers here that cover much of the same ground. You might find the information in some of them very helpful.
How do I diagnose the source of focus problem in a camera?
Pictures of surfers start in focus then go out of focus?
Why can't my SLR autofocus on certain parts of a scene?
Focus point causing unsharp images?
