One thing I would like to see are non-Starfleet missions.
Let me explain:
Let's say you come across a character that will have "things" he or she needs you to do. You could go to his planet (can't use communicator) and he or she will have various missions for you. It could be a parallel or independent set of missions from the original story-line. But they could provide some side entertainment.
And they can be serious (need you to protect so-and-so) to downright goofy (go to starbase "x" and get a pie from the bartender). The Klingons could have similar missions ("Go kill me a wild targ" and "get me more bloodwine").
Similar to the Zelda side missions, but this would be with just one character. A former admiral, a mad scientist, old Dahar Master, etc...
It would provide some relief from the constant fighting and could provide some longevity because you would have to actually fly to the contact in order to get the next mission and fly back to get your reward.