Communication may be provided from a first communication device over a multiple-input-multiple-output (MIMO) wireless channel to a second communication device. More particularly, feedback may be received at the first communication device from the second communication device, with the feedback including a precoding matrix selection from the second communication device. A representation of a speed of the second communication device relative to the first communication device may be generated. Responsive to the representation of the speed of the second communication device indicating a speed that is greater than a selection threshold, a generalized precoding matrix may be selected that is different than a precoding matrix indicated by the precoding matrix selection from the second communication device. Related devices are also discussed.