After experimenting a little with variable time steps, I switched to using a fixed time step to update my game objects independently of the current framerate. When things are being rendered, I interpolate each object's position, rotation and so on between the last two states.
However, what do I do the first time an object is being rendered? There is no previous state I can use, since the object has just been created with its initial state.
You could run one extra update step in the background before rendering anything, so that you'll always have two states available to interpolate between. Or just make the "initial previous state" a copy of the initial state.
It doesn't really matter much what you do, since everything will be fixed anyway after the first real state update, which will happen a small fraction of a second after the game begins — too soon for the player to really notice.
Edit: For objects created during the game, you could always extrapolate their position backwards to get an approximate previous position. This may look better than just having the object sit still (or be invisible) for one tick. The extrapolation still doesn't have to be very accurate, since it will only affect the first tick of the object's movement.