Hi Ryan,
For your budget, a lot depends on how you process your negatives and whether you are married to the idea of square format MF. If you are printing in a darkroom with a decent enlarger lens, the jump to MF from 35mm will probably be significant, even a relatively cheap and cheerful MF camera with a decent lens compared to your Leica, just due to the size advantage and lesser degree of enlargement. If you scan, however, there is the question of flatbed vs. film scanner. It's really hard to find film scanners for MF vs. 35mm. A dedicated 35mm scanner will outresolve a flatbed, lessening the MF advantage in terms of resolution, although the finer grain will still show itself. If you are stuck with a flatbed, the biggest negative wins, and you will see a distinct improvement with MF, and preferably 6x7 size is the way to go.
For your budget, you can get a pretty good Yashica, Minolta or Rolleicord TLR if a normal lens is enough. If you want interchangeable and square, Bronica SQ-A will do it. If you are not married to the square format, the field opens up with Bronica, Pentax and Mamiya all offering good 645 format systems, which are very complete. Fuji has some 645 rangefinders that might fit your budget. Hasselblads and 67 format SLRs and rangefinders won't fit your budget.