Only you can decide if the move to medium format is worth it, but I'd say that if you're doing mostly landscapes then I'd say you should strongly consider the change. 35mm is a great format if you need to move fast or if you're travelling and just don't have the room or the willingness to carry a larger camera, but in the end the very best 35mm equipment can't give you the image quality of a decent medium format camera.
The price on used medium format gear has dropped dramatically. (I picked up a Mamiya RB67 Pro-S system last year for around $400 complete with lens, back, and finder.) There has been a glut of medium format equipment in the market as professionals have been dumping it for digital.
Your willingness to carry a camera based on the size of the system will help you determine which format is right for you. If you don't want to move up too much in size and weight, a 6x4.5 system is a good choice. Even at the smallest medium format size, you get a negative that's very large compared to 35mm...and that can deliver quality that's beyond the best 35mm equipment. If you're willing to carry something larger, I highly recommend the 6x7 format, as it easily enlarges to the standard paper sizes.
KEH carries a wide selection of used equipment, and they have a great return policy. Note that my RB67 system came from them, and was marked as "Bargain" condition. Other than some rub marks on the bottom of the camera near the back, the camera looked and operated as if it was nearly new. Check out their web site. I won't bother recommending specific systems, as the web is chock-full of sites with more information that I can possibly give you.
(I am tempted to mention that, if your shooting is generally slow and contemplative, you might consider a 4x5 system...but that's a whole other issue.)