My favorite "space sandbox" game has always been Escape Velocity: Nova. It's the third game in the Escape Velocity series and easily the best of the bunch. Despite being made by a typically Mac-only developer (Ambrosia) it has been officially ported to PC and runs great even on really, really old machines.