I've done something similar to you. I started 3-4 months ago. I've put about 500-600 hours in since.
You will have a hard time finding groups for most things in normal mode, beyond a few key missions. This is especially true in prophecies. As a result of this, you will spend a lot of time soloing with H/H (Heroes and Henchmen). Heroes are like henchmen you can configure. They have access to all the skills you've unlocked for your account. Early on, this means they're kind of crappy. As you go through the game and learn more skills, they become considerably better.
All 3 of the main campaigns are roughly segregated. There's some mild cross-over, but they're definitely not serial. As a result, there's no reason to play Prophecies first (beyond the skill quests).
There's a type of skill in this game called an elite skill (it has a yellow border). You generally learn them by capturing them from enemy bosses with a Signet of Capture. They're usually a lot better than an equivalent non-elite counterpart. You will find that a lot of builds are based around whatever the elite is. You won't have a chance to pick up an elite skill in prophecies until extremely late in the campaign.
Were it me, and I had to do over what I did, if you didn't care about the LDoA Title (Legendary Defender of Ascalon) for HoM purposes, I would start an Assassin in Factions. The reason multi-fold. Factions is the quickest leveling (Within the first few hours, you'll be level 20). It has the quickest access to skills. As an assassin, you have a lot of your useful skills front-loaded, and a skill trainer in the capital city that has 99% of your factions skills to train. You will also unlock access to the Ritualist, which is a strong hero class. H/H seem easier to manage as a melee class, as they'll hang in the back while you're getting focused-fired. Assassins also make decent farmers, and your AC and energy gen allow you to use odd builds for certain situations you may need to spec out of your main class.
The only bad part of Factions is that it sort of throws you in the deep end. Starting in Prophecies, it wasn't really all that hard till you get to the Desert. In Factions, once you get off Shing Jea, the difficulty ramps up. It may be easier to put it on hold and move on. If you want at this point, you could go to EoTN or Nightfall to pick up more Heroes (You'll only have M.O.X. at this point unless you bought merc heroes).
Nightfall is easier than Factions, though I found it a lot more tedious. The areas seemed larger, and the groups in them were always astoundingly large. Normal-Mode Nightfall just seemed to be about packing as much AoE damage together as you could and running forward.
EoTN gets to be harder as you go on (as it was meant for people who were already leveled up and geared up). So, if you go that route, you may just want to grab the first heroes and then head to one of the other campaigns until later.
Once you have some skills and heroes, you'll find that Prophecies is a lot faster. The Prophecies map is a lot larger, and includes smaller group compliments, which seems to drag the areas out (for me at least).
All 3 campaigns have sections in the beginning where it's meant for local players. You can still access them as a "foreign" character, but you won't get the XP/Skill Point bonuses for completing them. From a story perspective though, you're not required to create a character from each campaign to experience these if you don't want too (The exception to this being Pre-Searing Ascalon. The only way to experience that is to create a prophecies character. But since you had one already, I'm sure you've got that down).
So, skills. There's a limit to the number of skills you can learn with a character at any given time (You can earn more skill points, infinitum). As a result, if you want to unlock skills for heroes, you may wish to create additional characters. Most of the campaigns have some quests you can do to learn non-elite skills for that character's current classes. These quests are only available to "local" characters from that campaign. In Factions and Nightfall these are confined to the starting island, so you can crank through them pretty quickly (and in Nightfall you have hero skill trainers to speed up acquisition). In Prophecies, the quests range through 3/4 of the story and are quite long and extensive. You'll have to manage your time to see if it's worth creating Prophecies characters, or bring in foreign characters to buy the skills to unlock (or buy the unlock pack in the store).
I will say, if you're going for HoM points, if you want to get the Legendary Skill Hunter title, you will probably want to save the skill points on your "main" character for capturing elites. Use "alts" to unlock the others.
Finally, the guild wars wiki (
http://wiki.guildwars.com ) is an astoundingly useful resource. It's especially true for missions, as more often than not the mission is bugged in some way. I found in the end, I could save myself a lot of annoyance and mission restarts by looking at the "notes" at the end of a mission before I started it to home in on the "bugs" section. This seemed especially true in Nightfall where both missions and quests, people would get stuck on parts, randomly teleported for no reason, didn't respond if you did things in a certain order, or what-have-you.