Needless to say, you should be able to make it to the bridge without difficulty. Just follow the only path forward and try not to get caught in any explosions or crossfire.
AI Constructs and Cyborgs First!
As you leave the bridge, you'll come across your first enemies on Legendary. Three grunts. Only peek in far enough to shoot one at a time. Aim for the head and nail them each in turn. Step back through to door to recharge as necessary.
The next encounter in the mess hall is your first real fight and can be very nasty. Get through this battle as fast as possible. You want to do as much as you can while there are still marines around creating a distraction. First, pick up the assault rifle in the doorway. Switch back to your pistol, zoom in and look for a lone grunt. He may have survived the onslaught of your marines and he needs to go down. After he's toast, switch back to the assault rifle and reload it while you're running straight ahead at the two elites in front of you. If you can club them with your rifle from behind go for it. If not, just lay into the closest one with the assault rifle, bashing and even reloading if necessary. Pick up the pulse rifle it dropped, ditch your assault rifle, and proceed to blast the other elite, being careful not to hit any marines. The pulse rifle you just picked up absolutely rules this level in my opinion. I say this because it can quickly and easily dispatch elites, even from long distances. Once you start connecting with shots, elites will just stand and twitch while you pour on the hurt. They don't have any room to dodge like they do in later levels. As usual be careful not to overheat, but even if you do, they're usually so mad by that point they'll rush you and you can melee them or switch to your pistol, which you should still have at this point. So back to the mess hall. Head towards the new group of enemies at the far end of the room. Three elites and several grunts just showed up to ruin your day. The marines should be taking a lot of fire for you, so pause to dispatch a few elites or toss a few grenades if the opportunity presents itself, but soon you should head through the enemy and through the doors they used to enter. Once you're out of the mess hall, clean up any grunts in this next hallway. You can then peek back into the mess hall and take out one enemy at a time without too much of a problem. Remember there are two entrances to the mess hall from where you are now. Use them both. Definitely take out as many elites as you can while peeking in. If that's a problem, just go for grunts. If you're pulse rifle runs out of ammo, run in and get another one. Once you've killed all the grunts the remaining elites will rush into the hallway after you. Leave a grenade for them to run into and mop up any leftovers. Congratulate yourself and go scavenge the battlefield for grenades, a health pack, and the fullest pulse rifle.
Follow the hallways (bashing an elite in the back on the way) and you should come across the first boarding party blowing open a door into the ship. Immediately after you see the explosion toss a plasma grenade into the doorway that was just blown open. Follow it up with another thrown deeper into the alien ship. After they go off, run in and finish off any leftovers. Don't pick up the overshield yet! Follow the hall and you should come across a few grunts and an elite in a darkened hallway. Toss them a grenade to soften them up. After finishing them off, then you can go back to pick up the overshield.
Follow the hallways until you see some marines fighting ahead of you. Turn right into the hall before you get to them and follow it around to the left. You should be in a nice flanking position now, so start chucking grenades and blasting away. Many waves of Covenant will show up, but they all seem pretty concentrated on the marines ahead of them, so they shouldn't be much of a problem. Especially since you want them to take down your overshield. Yes, you read correctly. Leave one grunt alive to take down your overshield. You can't pick up a new overshield if you still have any vestiges of an old one left. Go back and pick up a fresh one, and grab that health pack on the way to the next area if you need it.
Next, you'll see marines fighting on your left down a darkened hallway. Ignore them and follow the hall ahead, then left. Drop a grenade into the middle of the Covenant and blast any grunts nearby. As before, the elites will focus mainly on the marines and should be easy to take down.
The next group of Covenant has already blasted a way onto the Autumn. Too bad you couldn't catch these guys as they boarded. This section is pretty straightforward, though not necessarily easy. Use cover often to recharge, throw those grenades, and try to focus on one enemy at a time. Take out grunts first to reduce incoming fire, then elites. After you've fought your way past them, grab an overshield and scavenge as usual.
After crouching under a door, run through the next hall until you can just see a health pack on the left by a door. There's a piece of junk just to the right of the door, but you should be able to squeeze a grenade between it and the wall. Aim for the doorway and you should blow up a lot of this group. Back up and turn to your right. There should be a doorway that leads around to a flanking position on the remaining troops. There will probably be a lone elite here to blast through. Toss another grenade once you finish him off and follow the hall around. Mop up any survivors moving back and forth between the main hallway and this flanking hall. Once again you want your overshield to get depleted here so you can go pick up another one. If you have a partially damaged one, you can take it down yourself by bouncing assault rifle bullets off an energy shield. You'll definitely want a full overshield for the next section. You should also grab the health pack even if you're only moderately wounded. You're going to need all the health you can get for the next battle.
Next comes the stairs. This is probably the hardest part of the level. Rush in and run straight up the stairs to the top level. When you reach the top head left and go recharge in the corner of the room (that's the corner immediately on your right and up one level as you entered this room). Blast Covenant only if they get directly in your way. Now if you're facing the middle there should be a door to your right and the exit from this room further around the landing to your right. Take about five seconds to blast an elite if one's nearby then head to the door on your right. It should be opening slowly for a pack of elites and grunts. As soon as the door is open wide enough, drop a grenade in the center of the room. This should blow them all up, but instead of staying to watch continue on around and exit the room. As soon as you get out, turn right and bury yourself in the corner immediately on your right as you enter this room. There isn't much cover here just inside the door, but it should be enough. Just peek out and whittle down the enemy one by one. Go back in the room after the top level is clear and finish off any stragglers on the bottom level. An elite and a few grunts should be down there. Scavenge thoroughly after they've been eliminated.
Go back up now and leave the stair room. You should be looking down a long hallway at a group of Covenant. From this far off, shoot at the grunts with whatever is laying around from the stair room. Use charged shots from those plasma pistols. You may not hit anything, but they were just going to go to waste anyway. Once you've thinned their numbers, move slowly down the hall running from cover to cover until your behind the energy shield. Toss a grenade, then peek out and blast anybody you can in the confusion. Repeat until everything's dead. Now there should be just a few stragglers between you and that well-deserved health pack. Again, send a lot of charged shots of plasma down the hall to make your job easier before moving in for the kill.
Move ahead and use your pistol long-range on the grunts at the end of the escape pod hall. Enter the maintenance shafts.
There are several exits from the maintenance shafts and you should use all of them. Peek out, throw a grenade or blast a grunt, then retreat and go to a different exit. The last exit empties into some hallways that lead back to the Covenant, so use those halls to fire from as well, then go back in the tunnels. Occasionally you get them so twisted up coming from different places you can walk right up behind one and bash him. Be patient, look for opportunities to take one out each enemy by himself, and whittle them down until they're all gone. The next hall probably has an elite in it, so be careful of him as well
Pass through the cryochamber and on to the next hallway. Blast the elite at the end of the hall from long range, but keep running forward. An explosion should make him easy to finish off. Retreat into the long hallway. Peek out and shoot at grunts. Be patient and a few more explosions should take almost all of them out for you. Head back into the maintenance shafts.
Take out some stress on the grunts in the tunnel, then when you see an exit in front of you run up and throw a grenade out of it into the middle of the hallway. Quickly back up and turn left. Move forward and take a right then throw another couple of grenades out of the blocked exit. Back up again, turn left, and go through the last exit. Turn left and you should see just the tops of a few grunts in the corner. Toss a grenade into their midst, then head back to the right to clean up. After securing this area, scavenging, and picking up the health pack, look for a blue cylindrical thingy by itself. Near it is a door, which will lead you to a few grunts. Take them out, then head right around to a nice little flanking spot blocked by some junk. Toss all of your grenades (you'll get a lot more soon) to soften them up, and then go back around through the halls or just jump and squat over the junk to finish them off.
Now for the last fight of the level. This part is fun and easy. Crouch down when you see a pile of frag grenades scattered in front of you. Slowly creep up to the pile and fill up, staying crouched the whole time. Move back, staying crouched and chuck all your grenades over into the fray, being very careful not to bounce one back towards yourself. Move back up and fill up again. Keep throwing grenades until you're completely satisfied that everything nearby has been blown to smithereens. Enter the maintenance shaft to your left if you're extra cautious and peek out of the exits looking for any leftover Covenant. Any stragglers should be easy prey for such a hardened veteran of this level. You'll know everybody bad is dead when Cortana tells you to leave. Get back to the escape pod and you're done. Excellent work. You've just finished your first level on Legendary.