There is no physical limit that stops you accelerating to any speed less than $c$ relative to your current momentarily comoving frame of reference. By Galileo's relativity principle, a boost from your present frame to one going $500{\rm m\,s^{-1}}$ requires exactly the same effort and physics whether you may be stationary with respect to a second observer, or whether you may be moving at some speed $c-\epsilon$ relative to that observer for any positive $\epsilon$ no matter how small. You gun's muzzle velocity will indeed always be $500{\rm m\,s^{-1}}$ relative to your frame, whatever your speed relative to the second observer.
Suppose you begin stationary relative to observer $A$, then fire your gun and boost to the rest frame relative to the bullet. Now fire your gun again, and boost again to $500{\rm m\,s^{-1}}$ so that you are in the second bullet's rest frame. As long as there is someone in each new frame who can hand you a new shell to fire and some fuel (or a catapult to fling yourself with) to boost to the bullet's rest frame, nothing ever stops you making the same step and the same $500{\rm m\,s^{-1}}$ boost.
However, at each step, your time axis is more and more dilated relative to observer $A$. So this observer sees the speed added by each step as smaller than the first, such that the effect of all the steps asymptotes to $c$ from $A$'s frame. This is the mechanism that prevents greater than $c$ relative motion between observers: from your point of view, there's no barrier ever to your accelerating indefinitely.
I hope this little thought experiment sequence helps.