Good idea on the Knowledge skills and Skill Focus. I'd also be happy with dropping Intimidate (and even some of Listen & Spot) to free up a few ranks for Knowledge.
Let's go with history and local and then see if we want to scrounge ranks from somewhere else.
For the riddling curse, should characters be allowed an (appropriate) Knowledge skill check to come up with the answer? Maybe DC = FF's Knowledge check plus a racial bonus?