I would not recommend most of the route from Odawara south on weekends due to the traffic. You could maybe head up towards Shuzenji and ride southward on the ridge, but that would mean even more climbing and you would have to get through some traffic first. The toll road north of Shuzenji is very scenic, but unfortunately off limits of for bicycles...
Ditto on Nishi-Izu. If you're up for a couple thousand meters of climbing I highly recommend going up Heda Pass, turning south towards Nishina Pass, descending into Nishina/Matsuzaki and then going across to Shimoda from there. I did this just yesterday and it was amazing!
If you're not up for the climbing I would go down the west coast from Heda to Matsuzaki and take 134 to Shimoda. Much more pleasant than the east side.
My experience is, that the coast road nat. 135 on the East side of Izu connecting Atami via Ito to Shimoda is pretty busy, lots of trucks and tunnels and generally not very pleasant. But it might be the shortest and fastest road to Atami. Road nat. 414 running North South in the middle of Izu is better but also busy and involves more climbing than going along the coast road. You also have the chance to cross 旧天城トンネル describd in "Izu Dancer" if you make a small detour: http://goo.gl/maps/sHpyf
The best alternative, as already described, is to ride along the west coast, or a mixture of west coast and inland roads. Start at Mishima, nat. road 414 to Suruga bay (unpleasant road), and then along the cost pref. road # 17 to nat 136 and inland on road 411 to Heda and Nishina pass. Some serious climbing and not that much water refueling chances, but nice views and great, empty roads. Then down to Matsuzaki and further South along the coast. But not too long: There is a nice climb an pref. road 121 over Hebiishi pass and then a wonderful downhill sectin almost all the way to Shimoda. One of my favourite roads in Japan.
Here are some of the Izu rides from the Positivo Espresso Blog for more infos:
The trip out of Mishima can be made a lot more pleasant by following the Kano River （狩野川）. There is a cycle path most of the way, and nice quiet roads that can be followed pretty intuitively the rest. Just keep the river in your sights. It probably has a little less foot traffic than Tokyo river routes. You can do that until Shuzenji, then follow Route 18 for a nice climb up Heda Pass.