Got it! I now have Mission 1-5 on Normal completed with all Golds. Here is what I did for Mission 4 & 5!
Mission 4: When you are attempting the Gold AI in mission 4, use the first sub with the Lightning decal. It took me almost 2 hours of decal experimentation to get this Gold Medal. The lightning decal increases the speed & distance I believe of your torpedoes. In Mission 4 the key is to get to the boss significantly quicker than the AI. There is A LOT of wasted time spent waiting for those face boulders to crash through the floors and that is where you are expected to cut time.
By firing your 'lightning' torpedoes slightly off screen you can break the pillars before even seeing them. You almost can dive right through the floors at close to full speed as soon as you approach them if you properly make use of this lightning decal. When you get to the boss, as the screen shifts towards him at the start, fire one missile to damage him immediately. After this is done, get in his face and start firing missiles. Be persistent, but learn to space your missiles so you don't waste a shot during his recovery animation.
If the boss begins to do his 'shell charge' concealing his tentacles, go to the bottom of the ocean floor and get ready to fire your vertical missile. I believe the boss dies in 4 (or 5 shots). You will notice that the AI has positioned himself at the sea floor as well, readying his vertical missile, going for the final kill. Try to position yourself ahead of him so you can get your final vertical missile kill before him. If you follow these tips you are most likely going to get the Gold. This was the hardest thing to do so far in the game, imo.
Mission 5: I surprisingly got this Gold only after a handful of attempts. Choose the 3rd sub and use the Bull decal. Play normally up until the boss. As you surface towards the boss, immediately begin to fire your missiles! You need to kill this boss on his first retreat to the left, so its got to be fast! Position yourself on an angle so you can fire your torpedoes into its weak-point.
I am sure most have noticed that when it opens its cargo hatch you can deal more damage. Well, this is your time to shine. Just remember to space the 3rd subs missiles properly so you don't waste any shots. If you fire them all at once only 1 or 2 will hit. You need to make contact with each missile. As the boss begins to shift to the left you must begin to follow it and continue to fire & chip away at its health. At this point the boss should be near death. Take the damage if you must and just focus on following it and firing. And that's pretty much it for this medal.
Today, I am hoping to finish up Normal so mission 6 & 7 are next. I already have silver on 6, but I haven't even earned a single medal on 7 so I've got my work cut out for me! =)