I wrestled with the same question for a while.. I chose black because I thought it looked more classic/proper, even though I thought the Cyan contrasted so well with the screen.

Having said that, i put my phone promptly in the case and suggest you do, too.. so the colour of the phone may not be all that important if you can find a case with a colour you prefer.