After a long trip you may wish to spend the night and relax before boarding a bus. Butuan has some interesting sights, and you must travel through Cagayan when leaving the airport so just grab a taxi at the airport and ask for a hotel near the Divisoria, safe pleasant and nice night time walking.
the Gingoog motel is the only place to stay unles you are willing to stay at a boarding house, not recommened. Contacts can be with those who have private rooms to let, if you know someone in town.