If you and your fiancee are relatively fit and aren't afraid of heights, the best way to enjoy Taroko is by hiking up the Zhuilu Old Trail, which is several hundred meters above the main road. You'll need to apply for a mountain entry permit in advance, but trust me, all the mafan will be worth it. As for lodging, I highly recommend Silks Place. It's not cheap, but you'll be WITHIN the gorge. Swimming in the outdoor pool under the stars and listening to the streaming water was a pretty amazing experience. The hotel also has bikes you can rent to get to other hiking trails.