I have had the interlocking mats on a concrete floor for about 6 years, not expensive as they came from harbor freight. Surprisingly they have held up very well and appear to have a few years left in them. In addition I wear sketcher shape ups, which I have found to be very comfortable with lots of cushion. A lot of people, like my wife, have problems with the shape ups, so walk around the showroom for a little while before buying. Of the two, I would go for the mats first.
I do it right, cause I do it twice.