自分なら・・・

先ず、早朝到着で深夜出発の便を利用なら
空港へのアクセス方法を考えて
それに合わせて利用しやすい地域の宿泊先を探すかな？

朝早めの時間でチェックインまで荷物だけ先に置いとける、
出発日もチェックアウト後の荷物を預かって貰えると観光には身軽で望めるし。
宿から荷物を持っての空港間のアクセスの楽さ加減も考慮に入れると思います。