3) Change the characters over time

Players are kind of funny, they'll be secretly bored of playing the same characters throughout the game but they'll never change them because they've grown familiar with them. Force them to mix up their teams. I think this is actually a major part of what makes Pokemon consistently engaging. You rarely keep Pokemon on your team for more than a couple of gyms, so things are constantly freshening up. As long as you can justify the change with your story, the player will love it.

So very true. One of the best moment I've got with each RPG that I trully love is when my oh-so-well-built-strategy gets wrecked by the sheer forced party change!
(SPOILER ALERT!)

Chrono dies in Chrono Trigger! You have to make yourself a new party that consists of 'other people' which, so far, were considered secondary party members.

Th
The world dies in FF6! You start off with Celes (not Terra) in a new broken world, recovering party members one by one, in a much different order!


A big part of the fun in RPGs (and in games) is mastering something, and then, the rules no longer apply. Changing the player's party makes an otherwise mundane battle which you would normally go through using the same strategy, an altogether new challenge you need to overcome with new tools. Even better, once your original party becomes available again, given the choice, you might have changed one or two party members because you've liked them.
The best RPGs tend to break down portion of the scenario to certain characters so as to let you experience them in different contexts so that you don't pick your favorite members based on sheer looks.

1) Have an interesting and dynamic combat system

You have to think of battles as puzzles. Is the puzzle fun to solve? In most final fantasy games it isn't. You press "attack" and maybe cast a spell until you win. The differences between the options are relatively small. By comparison, the Shin Megami Tensei games usually have very involved battle systems where you need to account for elemental strengths/weaknesses and turn order in order to not get killed. Organizing your team and then playing optimally against opponent's strengths and weaknesses is what let's SMT games get away with being so grind heavy. I know that "Make it fun" is a pretty bad suggestion, but I think it's important to stress that pressing "fight" 6 times makes for a pretty boring game.

Probably much easier said than done... and very vague too.
Also, often, making this battle system more fun will make battles longer.

Quoting from the original question:

make sure these random battles don't get too tedious. How often is too often for these battles? Is a variety of enemies important, intelligent AI?

Tedious: Too long, slow, dull, monotonous. 2 of the words emphasize the time & tempo and two emphasize the quality.
Making a kickass battle system will improve on the last two while taxing the first two. The question here is whether you can make up for how much longer the CBS gets with the quality you've injected, and more often than not, you'll realize this may be an utopian dream.
I'd rather stick with the classic battle system with just slight twists.

As far as "how often is too often" is concerned, I'd have to go with: give the player a choice. In the end, not all players are exactly alike, and you want to make that fun for as many people as possible. Having mobs visible on-screen with movement AI out of combat really helps the player decide whether this is a battle he wants to take.
The concern here is that there may be an XP issue at some point where the player skillfully dodging all the battles will be weaker, but it shouldn't be.
In Dungeons & Dragons, when you escape from a battle, it considers you have survived the encounter regardless. The fact of being crafty should be rewarded.
I would be as bold as to suggest that, whenever a player levels up, you could check the ratio between battles fought and battles escaped/avoided to determine which stats should increase (strength vs speed for example). That way, the leveling up would emphasize the playstyle of the player.

As far as AI is concerned, I think a pretty nifty AI can really come a long way. The idea is not necessarily to make it random (although that's much better than a weak pattern) but to simulate pattern, aka, define complex situations and conditions that make the critter's behavior more believable.
Most AI I've seen were all about: if over 50% HP, bash, if under 50% HP, heal self or drain attack. That does represent an ok sense of realism, but it should read that way:
if over 50% HP, attrition on player's party, if under 50% HP, unecessarily prolong the battle (because that's what happens when a unit self-heals).

You should really consider the tempo of the battle that you seek to establish, and this should command the tone you give to your AI, much more than attempting to make the enemies adopt realistic behaviors that the player can relate to (as it could resemble their own decision process for example). Tossing a few enemies with more or less realistic properties can be nice, but you need to vary with unexpected strategies (especially with beasts and animals / monsters). Contrast here is the key. If all your monsters are berzerkers, the player will feel bored, but if most have an instinct of survival and tend to go turtle when shit hits the fan, they'll be surprised to see that vicious critter striking you with their best arsenal of skills once its down below 10% health. Call them kamikazes, they do surprise, and that's not mundane.

I wouldn't say that the variety of monsters needs to be overkill. Rather, I'd focus around a few archetypes the player can relate to, so they can instantly remember what they're up against. The real fun comes from putting them into action in different numbers.
Imagine the following archetypes:
Tanker (High HPs)
Glass Canon / Striker (High dmg dealer)
Support (Boosts Def & Atk of all allies)
*Suppose that the Glass Canons will always counter-attack so long as there is a tanker present
*Suppose that a Support will turn into a Uber Glass Canon if last survivor
*Suppose the Tanker's attack scales accordingly to the amount of other Tankers present

And imagine the following scenarios:
1 X Tanker
3 X Glass Canon / Striker

2 X Support
2 X Glass Canon / Striker

3 X Tanker
1 X Support


Who'd be your primary target in these encounters?
I would assume it would shift based on which critters are present and vary based on the overall impression you get from the encounter at first sight.
Critters that are sometimes major threats may appear like the weakest link and vice versa depending who is around them.
It is a puzzle for player to solve than to establish his target whenever one of their character is ready for action.