I thought of a trick to get it down to 2 queries! Combine both techniques:
Code:
$regions = new Region();
$regions->order_by('name')->get();
$city = new City();
$city->include_related('region', array('id', 'name', ...));
$city->order_by_related('region', 'name', 'ASC'); // order by region first
$city->order_by('name', 'ASC'); // then by city name
$city->get();