During booting, press the asked key (I?) to see the verbose output of the boot process (not just the bar and one-liner). You see different services starting up: which one of them takes the long time if there is no cable connected? Is it sendmail, perhaps? In that case simply use the system administration tools to make that service not start when booting (you shouldn't need sendmail, for example, on a personal desktop - I don't, anyway).
I don't see why having or not having an internet connection could affect programs' quickness other than those that do need internet to work properly.