temps: Playing a campaign, due to the story and unique or novel circumstances of the campaign, not to mention the cinematics, atmosphere, and story that typically accompany it; is typically more interesting to me than simply playing a random skirmish map that allows for allied factions. I just thought it would be fun to play with a friend... that's all.
Ah. I wanted to check whether it was more story aspects or "play with a friend" aspect that you cared about more, or if you were really looking for "lets play through a series of missions together".
Some single scenario maps do have elements of story (but not all), though generally a more involved story is achieved via a map designed for a single player experience because there are fewer variables that the map maker has to deal with, like victory conditions.
Most of the Heroes 2-4 campaigns are simply a series of scenarios that have an overarching theme. For example, the first "Good" campaign in H3 has the theme "Recover from the surprise Demon attack", where the first map is all about establishing a beach head, the second map is gathering allies, and the third map is gathering the troop production you need. The first "Neutral" campaign in H3 is about being a mercenary leader in a time of trouble; the first two maps are working for two different sides, while the third map is picking one of those sides to support in a land grab.
I haven't played all the scenarios that ship with H2-4, but H3 is probably your best bet for what you're looking for. Some of the scenarios do have more than just a single pop-up text box after you start the map, like random events you may stumble across while playing, or events based on time triggers, but you won't find cinematics in any of them. I also suggest poking around
Celestial Heavens to see if you can find anything that looks appealing.