C/C++ is a good start.
Mac Desktop development would also be a good background considering it's the only other widespread use of Objective-C.
C# is ok, but isn't directly related to the iPhone (unless, of course, your client is ok with you developing the app in MonoTouch).
Other development for mobile platforms would definitely be another plus. It shows that you have the experience at dealing with issues that you'd only find in the mobile space. If those mobile applications where for touch-screen devices, that's yet another bonus.
Personally, above all else, I'd be doing my best at showing my ability to adapt to change quickly, learn new things, and be instantly able to apply them.