I enjoyed GEB, although Hofstadter's style is...something, for sure. Either way, there's plenty to think about in that book, and a surprising amount of fun motivation for learning discrete math.
I seem to keep coming back to the style issue with my reading list. On the one hand, it'd be nice to zip through books easily. On the other hand, when all the choices you've laid out have a reputation for being word soup, there's less incentive to jump ship to easier waters. I did go and buy a copy of I Am A Strange Loop..I enjoyed GEB, although Hofstadter's style is...something, for sure.
I didn't find it wordy (but maybe that's me). There are a lot of puns and wordplay and odd stories. I guess the best way I can explain it is it's how mathematicians and scientists write when they're writing for fun. Something like this or Cliff Stoll's writing. Maybe that's the thing I liked most about it: it is a bunch of "weird math", but Hofstadter is having so much fun telling you about it that I couldn't help but enjoy it. (Then again, I'm a grad student studing "weird math" partly because I read GEB years ago, so YMMV.)