You could simply "slow down" the entire frame (physics, ai, rendering, everything) to accommodate for lag. That way the game will only slow down when there is lag, but not be jerky. I wouldn't be terribly concerned with it, however, as no one really expects a game to look great when its lagging.