My lovely lady wife and I have only ever rented bikes twice while on holiday, but one of those occasions was in Gozo. And it was fun! The roads weren't too busy at all, nowhere near the madness of mainland Malta, except possibly from the ferry port at Mgarr into the capital Victoria. User is spot on about the road surfaces and the hills (it was about fifteen years ago we biked there, mind you). We did find one beautiful, smooth black resurfaced gradient running down into Marsalforn from Xaghra.
If you go during the hunting season (Autumn-ish, I think) be aware that some of the smaller tracks may have been roped off by bad-tempered old men with shotguns who will not make you welcome. Also, it you're hoping to see the beautiful Azure Window at Dwejra . . . it collapsed into the sea back in March.
