Going across the Moors can definitely be tough, particularly on the minor roads. However the Pickering to Whitby Road is beautiful and relatively easy to cycle, but quite busy.
An alternative, which I'm planning to do in a few weeks time, is to go round the edge of the moors. You can take Sustrans routes 65 from York or Thirsk along the east side of the Moors, and then cut west along the beautiful Esk Valley to Whitby. From Whitby there is a cycle track (cinder surface) down to Scarborough which offers some spectacular views of the coastline but can be a bit bleak in bad weather. From Scarborough you could pick up a train back to York, or cycle if you are feeling really keen. This route would be far from flat but would be much less hilly than some of the direct routes across the moors.
There are nice Youth Hostels at Osmotherly on NCN 65, Whitby, and Boggle Hole (which is one the cycle path from Whitby to Scarborough). There's also a Youth Hostel in Scarborough but haven't stayed there. Can also recommend a particularly nice B&B in Whitby if you fancy something a bit more up market.