This is the sort of thing that hash functions are designed to avoid.
Since getting closer words does not get you a closer hash, usual optimization algorithms (like genetic algorithms, simulated annealing, etc.) are not going to be helpful.
Perhaps I'm missing something, but I think brute force and luck are going to win this contest, assuming that SHA1 is not broken between now and July 20th. If you want an iPhone 3G S, you should probably just head over to the Apple store and buy one and spend your valuable time on something else.
I think the main challenges are deciding how to manage the brute force effort.
You can precompute a lot of hashes, and then search them on the contest day.
Or you can run it only during the 24H of the contest, and only store the result which is nearest.
And the second issue: how much resources to invest. A high CPU on EC2 is $20 for the day. Another doubles the price, and doubles the number of hashes you can check.
EDIT: The restrictions they place on the input makes rainbow tables kind of pointless. Just partition the search space (i.e. the permutations) pick a piece of it at random, and send it to your brute forcers.
EDIT2:
Back of the envelope: you will be able to try about 100million hashes for $20.
