if you have children. If so, go on the Explorer.
We just returned from the mega AOS. We are not big atheletes either, and only utilized the putt putt. However, the ship was absolutely amazing!
We have been on several smaller ships, including the Vision (sister ship of the Grandeur). We loved the Vision and thought the size was perfect for the two of us, however, the children would have been bored. We were childrenless for our last cruise as well, but can't wait to take them on another large ship.
Since you are first time cruisers, I think you will be fine with either ship. If one is a lot less than the other, than go with that ship.
May I suggest a balcony stateroom?
When are you thinking of cruising and what areas do you want to see