UPDATED:
There is an easier way! First, assign your legend to a variable when you create it:
leg = plt.legend()
Then:
for lh in leg.legendHandles:
lh.set_alpha(1)
OR if the above doesn’t work (you may be using an older version of matplotlib):
for lh in leg.legendHandles:
lh._legmarker.set_alpha(1)
to make your markers opaque for a plt.plot or a plt.scatter, respectively.
Note that using simply lh.set_alpha(1) on a plt.plot will make the lines in your legend opaque rather than the markers. You should be able to adapt these two possibilities for the other plot types.
Sources:
Synthesized from some good advice by DrV about marker sizes. Update was inspired by useful comment from Owen.