I would like to say the Paramedic missions were the hardest on the game, trying to complete the levels was kind of easy but I really hated when I was so close and then the Ambulance would flip and blow up, it was really annoying for me.
I used to dread the paramedic/fire missions. For the fire missions, do them right at the start of the game. As you leave the cemetery for the Grove, look for the fire truck. You'll go through the skate park usually, but go around the right hand side instead and look for the fire truck. If it's there, snag it and take it with you to the end of the mission. After passing, go to the beach area just east of Ganton. Start the fire fighter missions there and you should be fairly lucky with traffic spawns. Occasionally you'll end up in the countryside but the game won't take you much further than that.
As for paramedic, go to Montgomery and do it there. There's a hospital and an ambulance waiting for you. Knock the doors off with any melee weapon so your patients can get in and out quickly. It might not feel like it, but this extra time saved will make the entire slog less painful. The tedious part here is the back-and-forth driving you'll do. Obviously you'll be making a minimum of four full trips by the time you hit level 12, but often the patients will be grouped together in clusters of three or four.
It's helpful to get these two out of the way early on, though vigilante is best left until you have decent firepower and a sturdier vehicle. That is, if you don't cheat/glitch your way through it.