Regular C strings may seem daunting the first few times, but once you get used to them, your need for inefficient Strings will plummet. If you post the section of code where the String is used, we shall see if we can refactor it into regular C char arrays (or C strings, if you will).
Another way to shrink your code would be to compress your data in some way, for instance using bit fields, or compressing boolean flags into bytes and access them via bitmasks, and so on. Again, it's hard to tell if this can be done without looking at the whole picture.
If you really need all your code, still another solution is to get rid of the bootloader and directly flash the program via ISP. This can be done if you either have a programmer or another arduino board.