If I started the campaign on Easy, can I change the difficulty midway? or do I have to restart from mission 1?

I think there's a difficulty attribute somewhere in the settings that you can adjust between missions. For Red Alert 2, it's a file called RA2.ini and for Yuri's Revenge, it's RA2MD.ini. Under the Options section, there should be a setting called Difficulty, and you should be able to set that to what you'd like. 0=Easy, 1=Medium, 2=Hard.

I could be totally wrong about that though, let me know if that doesn't work.

I think you can change by going into options and changing the difficulty to hard. I think i have done this a couple of times and it worked.

If you play on hard and you don't hit the par time, it will automatically load medium for the next mission, and if you beat par time there it will put you back to hard for the next.

I do not know if starting on easy will automatically bump difficulty up for beating it quickly.