How much of a role does the resolution of a texture play in load time?

I've finally gotten my first game released into the wild and, to keep things simple, I've restricted it to BlackBerry until I can get it out of beta state. So far, the biggest issue I seem to be having with it (and in reviews) is extremely long (15+ seconds) load times. Because my meshes are, at most 2-300 polygons and my scripts are relatively simple, I believe that the issue is stemming from having very large textures (some are over 2000 X 2000 pixels), but I haven't really had time recently to go back through and scale all of them down. How much of an improvement could I expect from cutting the resolution in half and what is a good baseline for texture resolutions for moble games?