On Windows, rebase changes the preferred load location for a dll and (I've read) can dramatically decrease application load time. Is there a similar concept on Linux and/or gcc?
In my experience, rebase doesn't really help a lot on Windows. Probably back in the day when dll's were smaller it helped more, but I think you are more likely limited by hard drive i/o performance now.
To answer your specific question, shared libraries on linux are quite different from shared libraries on Windows. I do not believe there is any similar concept with regards to rebasing. You can read more about shared libraries and dynamic loading here.
Here's another link, Dynamic Linking, that explains why rebasing isn't needed on linux so long as you use position independent code. In Windows, this isn't available, meaning rebasing has to occur at runtime. It should be noted that rebasing on Windows isn't guaranteed to make a difference on every system, just systems where the default base address of the dll happens to not be in use when you run your program.
Some distros come with prelink which does something similar to that. DT_GNU_HASH , which are slowly being adopted, furthermore speeds things up.
It scans all the executables and shared libraries, tries to determine and modify the optimal loading address for the shared libraries to avoid the load time relocation . Load time relocation is what can slow down application startup as well as use more memory - although the "problem" is much smaller than on windows.
http://people.redhat.com/jakub/prelink.pdf tells you how prelinking helps.