First off, I'd just like to say that KotC is a beautiful game, and I'll be happy with any sort of sequel, even if it just turns out to be a slightly different map and storyline.
That said, here's my ideas for how to subtly change the next game (hopefully for the better)
Larger Overland map (with "fog of war") -- Since the resolution for KotC 2 is going to be higher, hopefully we'll get a larger map anyways. Ideally, I'd love to see something similar to the maps in Fallout 1 and 2, where you can roam around gradually uncovering sectors of the overland map yourself, or have cities and other important locations revealed to you through dialogue with various NPC's. This could also be a useful tool for keeping some of the more difficult missions out of the way until the part is ready for them. (ex: there's a secret mine up in the hills, but you can't find the entrance until you track down the old miner and persuade him to show it to you on the map)
Save/Camping on Overland Map -- It makes sense that characters should be able to save/camp anywhere in the wilderness. However, just to spice things up, I'd have the party roll to see whether the night passes uneventfully, or whether they trigger a random nighttime encounter with bandits, wildlife, or other evil critters! This would still make staying in inns and houses desirable (since you can't be ambushed), and worth the $25-200 gold pricetag.
If you wanted to carry it a step further, you could give the party the option of leaving a character on guard (they don't regain HP/SP, but the chances of an ambush are reduced) or make safer wilderness camping a bonus trait for a Ranger character class.
Item creation can only be performed in cities -- You can make this a feature of the weapon/magic/clerical shops. It makes sense, and will cut down on late game "oh look, there's a bunch of red dragons or Balors in the next room, in the next room, better craft a bunch of dragon slaying arrows or something out of cold iron."
New Character Class: Ranger -- Basically, a character specializing in ranged weapons rather than melee attacks. They can use light armor (anything wooden or leather), and wield bows, crossbows, staves, daggers, and clubs, but nothing heavier. If possible, I'd also give them bonuses against animals and surprise encounters in the wilderness. (possibly also a save against Entanglement.) They should have the ability to craft basic items made out of leather or wood, as well as archery weapons and arrows/bolts of sleep and poison. I'd also give them bonuses to dexterity, reduced penalties for shooting in melee and around blocked targets, plus additional ranged attacks every 3 to 5 levels.
New Character Class: Monk -- Somewhere between a cleric and a knight, and specializing in unarmed combat. Monks get high dexterity/dodge/movement/initiative bonuses, as well as easier critical attacks, and resistance to most mental attacks and stunning. Like wizards and clerics, monks can learn a variety of techniques from scrolls they pick up as they advance in level. These moves are more like the cleave attacks of knights though, since they don't require SP and can be used repeatedly without resting. (Though some moves require a full turn to implement, or can only be performed when flanked by two enemies, or when one square away from an enemy, etc...) Some of their moves will have similar status effects to wizard/clerical spells (stun, sleep, blind, etc...) and can be cured or protected against in the same way.
Having a monk in the party would be a double-edged sword, since they're great at dealing out critical hits, can take out or stun 2 or 3 humanoid opponents in a single round, and almost always get the first attack, but lack the armor class of knights, are vulnerable to magic, and their attacks become less useful against large sized opponents with lots of resistances or aura attacks (like dragons). Still, while they may not be as good as knights when it comes to receiving damage, they're better than any other class at dodging, and higher level characters can meditate and cast a variation on the "false life" spell which allows them to soak up a few extra points of damage, which may just see them through a tough battle.
Allow players to choose between 3 to 5 characters for their party -- It all boils down to replayability. Since you pretty much have to play with at least one wizard and cleric, it'd be nice to have a few more options your second time around. I'd recommend allowing players to choose at start up whether to set out with 3 to 5 characters in their party, with experience being split up equally between the number of characters. The neat thing about this is that you wouldn't have to adjust the base difficulty at all. 3 characters will level up significantly faster, but it'll be a struggle just to stay alive. 5 will have an easier time of it, but earn less experience, meaning that they'll be taking on comparatively more experienced opponents as the game progresses.
Similarly, Have at least one randomized dungeon -- Again. I don't know how difficult it would be to implement, but it would drastically increase the replayability factor, especially if you had a couple of them. It wouldn't have to be terribly big or complex. You could even predraw a few dozen empty levels with one up and down staircase, and then have the game pick 10 at random and populate them with enemies. I wouldn't make them part of the main story or anything, just in case random fate deals out something the player can't handle, but they'd make good sidequests, especially if the bottom level is guaranteed to contain at least one weapon/armor/artifact that makes the trip worthwhile.