Velocity is relative. That includes a velocity of zero. There's no such thing as being "at rest" in an absolute sense. Right now you consider yourself at rest, but to the billions of neutrinos passing through your body every second you're travelling at nearly the speed of light! So the idea that things at rest stay at rest is the same idea that things moving with a constant velocity maintain their velocity. If they don't feel like the same idea, then you haven't yet come to a full appreciation of the principle of (Galilean) relativity.

The reason that it's hard at first to wrap your mind around the principle of relativity is that the forces due to gravity and friction dominate our lives. In our everyday experience, there's very much a difference between being at rest and moving with respect to the air, nothing we push keeps moving in a straight line forever at a constant speed, and everything that goes up comes down. Coming to terms with Newton's 1st Law requires understanding that we're surrounded by complex "special cases" that hide the underlying simplicity of inertia. It's not intuitive, but you can build up an intuition here.

On force...

While force is related to phenomena you're familiar with (e.g., pushing and pulling), ultimately it's an abstract quantity, and it's simply a fact that (net) force is directly proportional to acceleration, not velocity. If it helps, you can regard Newton's 2nd law as a definition: the net force acting on a body is defined as the body's acceleration scaled by its mass.

Also, don't confuse the net force acting on an object with any particular force acting on it. When you push the box and it moves at a constant velocity, it has no net force, but you are still applying a force to it. Think of it like this: the table is trying to bring the box to rest, and you're applying the force that's preventing that from happening. As soon as you stop pushing, the only remaining force acting on the box is due to friction with the table, and since the net force is now not zero, the box's velocity changes as it slows to a stop.

Actually, you have it backwards: an accelerometer in free-fall measures 0. If you're interested, read up on the equivalence principle, which is a cornerstone of general relativity.