I thought the third and fourth season were pretty good, myself. In fact, the 4th season format was, in my opinion, the best ever for Trek.
The fourth season format was good. But the episodes themselves were a little too much fanwank for me. Especially the Klingon plague episodes. The season felt like they said, "the average fan isn't watching anyone, so let's go mine history and create episodes around every tiny detail we can."