Which is the best way to present speed benchmarking along with speedups?
I agree that tables seem to be more effective in conveying the information you have. In order to make the speedup clear, you can add a column to indicate the relative speed:

Method         Runtime [s]       Relative runtime
-------------------------------------------------
classic        134               7.9
fancy 1        23                1.4
fancy 2        17                1


You could scale to the fastest or slowest depending in which direction you want to put your argument in the text, and you could use logarithmic scaling if the benchmarking results are orders of magnitudes apart.

Hans Mittelmann's simplex LP benchmarks have something like this across the top row of the result table.