I'd get rid of the holodecks so there can't be any further holodeck stories.
What would you introduce/change instead?
I don't think fiddling around with the character elements is as important as to get rid of what allowed for the bad writing.
Nix the holodeck.
Jeesh, we have this whole new quadrant to explore and the writers already have to do an holodeck story by ep12 of Beowulf in Heroes in Demons? This ship is looking for energy constantly and we're led to believe these are still running?
The holodecks always felt like a lazy way for the ST writers to say "We're sick of ST, so we're gonna write what we feel like and insert it into a space show." And the result is about as interesting as an adventure show in the 20th century following people around playing Nintendo and Sega.... over and over and over again. Plus heroes and demons was plainly a vehicle to get the popular EMH for the first time into a starring role (which escalated in S2 and peaked with the portable emitter).
There are only a few holodeck usages or eps per series that were worth watching. Minuet distracting Riker and Picard in 11001001. That two big Barclay eps in TNG. Vic Fontaine helping Nog get back on his feet. Maybe the first Barclay ep in V. Maybe the one where an alien falls for Tuvok. That's 2/3 or less per series. All of these advance the characters and worked because they were not "Oooh gee, look what we can make popup on our 24th century always faulty Nintendo!"
Voyager had a whole slew of bad ones. I'd explain that because the holoemitters has a usage lifespan and cannot be replicated, they'd are laid to the side for the EMH, which is more important to have than holodeck.
It would make what should have made what is a tense situation more tense by taking people's entertainment away. Then they'd have a reason to treat the EMH poorly as well. We never really see just daily life and struggles on the ship, this would have helped.
Reset Button
I would have nixxed the reset button. The ship isn't always nice and clean at teh beginning of each episode. No magical repairs. No magical maintenance without spacedocks. There is no feeling that this is an ongoing journey.
Forehead of the Week
Now that it's 2015, get rid of forehead of the week aliens and give us some truly bizaare aliens. Farscape did a much better job at this mostly without CGI over 10 years back with muppets and probably much lower budget. (Didn't care too much for the rest of the show, but the aliens themselves were good). Make this seems like an alien quadrant for once, not just the same old, same old.
Bar alpha quadrant aliens and most elements. No Ferengi. No wandering Klingons looking at B'ellana's baby as a savior. No magical contact with Star Fleet. No worm holes to Romulan ship captains. Lazy, lazy, lazy! Make the isolation real. The "will we get home?" a real question and not just an inevitable conclusion.
Misc
People died. A lot. It's time to get more recruits on board after caretaker. Some who will bring tension of one sort or another.
Allow tension. Everything don't need to be solved at the end. The crew doesn't need to be one big happy family.
Get fresh writers rather than recycled ones from the previous series. If it's supposed to be a fresh series, get fresh minds.
Have a series' roadmap. Not every detail needs to be mapped out ahead of time. But for a journey series, give the rough clue where the ship will be when, why, etc so half-assed endings don't happen. If a series gets nixxed before they're home, oh well, that's how the ball drops.
Characters
Neelix. Should have no relation with Kes. Should be very competent as a guide to a Tuvix like degree but an opportunist. Fully flesh out the hints of rogue about him. Nix the family friendly part of him. Should have a different character design.
Kes. More of a seer with her telepathic abilities cast out by her people. More competent than Troi.
Kim. Up his bromance with Paris. The two could have made each other more interesting.
Paris. To tell the truth, John Crichton from Farscape feels a lot like he was based on Paris in some ways. I can't find too much fault with Paris, but he vaguely goes into his accident but this was screaming out for an episode on its own, Locarno notwithstanding.
Chakotay. Dump the native american stuff to background elements. It's who he is, but offscreen and just hints onscreen. He doesn't talk about talking to spirit animals on the bridge just like Torres wouldn't be talking about Stovokor just like Paris won't be talking about the 10 commandments and Barclay won't be on about some Scientology stuff. They're Professionals. Don't have him fall for Janeway and instead make his promotion to XO contentious and on account of his bargaining -- Janeway doesn't have the manpower to run the ship and she and he know it. Threaten to walk off a few times and have his crew get a new ship. They get sick and tired of constant danger for Starfleet ideals.
Seska. Keep her on for longer. Rather than dealing with the Kazon, she double deals with them or better aliens. Let her be really in love with Chakotay but keep the Cardassian part, I like that.
Lon Suder. Keep him. No reset button. No get out of jail dying prematurely card.
Torres. Make her less whiny, angsty, and always on the verge of tears. Have her watch some K'Ehylr episodes from TNG. Or just invite Kehlyr's actress to this role.
EMH. Have people actually be rude to him because he's causing their holodeck inconvenience.
7 of 9. Just got too repetitive and too much of a Mary Sue on top, seeming to know everything. Drones by the very word to me seem to imply something dumb and almost instinctual. That's why they can assimiliate technology but not really innovate. Keep her haughty and arrogant but dumb her down from always being this Deus Ex Machina on call 24.... seven?
Janeway. She's fine. As is. Entertaining and believeably so in power. But terribly flawed. Except the show should have presented it in that light and not "The Captain's always Right" as Tuvok said.
This is a ragtag ship of misfits lost deep in space and not all of them get along. But it's never shown, just told. Over and over again. What they showed was TNG on a normal day.