We have done both. We absolutely ADORE HDDR, and try to fit it in every trip, or every other trip. We also really, really enjoyed SoA the first time we saw it, and thought it was just OK the second time. The dancing is absolutely enchanting (for us) and the food is surprisingly good (except dessert, blech! but we were so full by then we didn't need it anyway).
Having said that, we only go to WDW every other year or so. I doubt even we would need to do HDDR 2 times within a few months! So my vote goes to giving SoA one try. If you don't like it, you never have to go again, and at least you'll put your curiousity to bed. I definitely recommend Cat 1 if you decide to do it. Our GREAT experience was in Cat 1.
Good luck!