In this work we study the problem of constructing precoders for spatially multiplexed multiple-input multiple output (MIMO) channels with close to optimal minimum Euclidean distance. In order to exploit the full potential of such designs, an ML detector must be used. Our design takes the decoding complexity into account and constrains it to a reasonable level. For our simplest case, the ML detector can be implemented by a Viterbi algorithm operating on a state space of size equal to the size of the modulation alphabet. The design problem will be relaxed by using precoders F such that F*H*HF is a cyclic Toeplitz matrix. Within this class of precoders, the optimal precoder can be found via linear programming. Of uttermost practical importance is the discovery that there only exist very few different effective channels HF even for large MIMO setups; thus, the optimization at the transmitter side reduces into choosing the best precoder from a small list. Receiver tests verify that our method improves upon the currently best precoder designs.