A good hotel close to Gaisano Mall is Go Hotels Butuan (rated 8.2/10 from 1,232 reviews).