Ok, its actually pretty easy to make choices feel like they mattered, though that was only one of many problems with Mass Effect 3.
Option I, change some missions. "But its a lot of work", "They had to release on time", "blah blah blah", "Blah blah Blah". The question was how to make choices matter, not why can't we make choices matter. Additionally, other games and other studios have managed to do it. The game needed more time anyway, as shown by the lack of choosable dialogue lines which are a constant in Bioware games, and the overall lack of polish in many areas, and the half-assed original ending - ect, ect, ect. Give more time, make a good game. Would much prefer that to a quickly released shitty game, and I'm sure most would agree.
As some examples; The rachni mission. Whether you killed or saved them, they appear and give the exact same mission in ME3. Here you have two choices, 1. If you let the rachni live, the mission exists. If you don't, it doesn't. 2. Either way, the Reapers bring back the Rachni. If you saved the Rachni, your Rachni Queen is in a war with the other Rachni Queen, and you enter this war to help your Queen. If you didn't save her, the mission is as is. The atmosphere of the mission would change a lot, as would a lot of dialogue. Mission structure should also change.
Another example would be the Quarian mission. If you'd advocated peace among the Quarians, and redeemed Tali, then the Quarians wouldn't have gone to war with the Geth. This would lead to different dialogue, even if the mission was the same. If Legion had survived, and his loyalty had been gained, then the mission itself could change. Re-writing all the Geth to not follow the Reapers would have them not follow the Reapers, and thus the mission would turn into defending the Quarian homeworld from a Reaper invasion, rather than fighting the Geth again. If you had just destroyed the station, civil war could have broken out among the Geth over the Reapers, and you intervene with the Quarians. If Legion hadn't survived, or his loyalty hadn't been earned, then the mission would be as is.
This could be repeated for near any mission in the game, as most of them reference choices or characters from previous arcs to some extent, however quite often it is just a model and voice change, with nearly if not exactly the same lines, and the exact same thing happening in the mission.
Option II is more the Mass Effect 1/Dragon Age: Origins way of doing things. You see your allies and choices play out, but they don't exactly do a lot. Choose the Salarians? You see Salarian strike teams moving in on Earth. Save the Krogans? You see hordes of Krogans jump out of their ships and charge the Reaper forces. Save the Destiny Ascension? You see her fire her main gun into an enemy Reaper, and tear straight through it. This changes basically nothing in the game, but it gives you a show to say "Hey, look, you did a thing". Its satisfying to see your choices play out, at least more so than having just "+50 war readiness", which is an arbitrary amount added to an arbitrary counter which really does fuck all in the end for most people. A bit more work, but a much better way of doing things than just one shared cinematic that looks near the exact same, and contains maybe 3 lines of dialogue difference based off your previous playthroughs. A good epilogue, the type the EC gives, would help a lot with this, as opposed to the crap that was given at the start. This gives emotional payoff more than practically changing things with the choices.
Option III is to have the ME2 way of doing things. Final mission. Your assets are the choices you've made. Who's loyalty you've earned. Who you've added to your team. You have to apply them to different tasks where they are best suited, and if they're not well suited, they either fail and die, or barely succeed and die. Would require an entire rewrite of the final mission, even if it did still have the same ending, but that's something I think needs doing anyway.
Option IV is to be brutal, and to lock out certain endings based on choices. Personally, this would be done better if you properly fought the Reapers, and had varying levels of damage down to utter annihilation if you made the wrong choices, however it could even be done with the current endings. Don't advocate peace with Quarians and Geth, and bring them together, no Synthesis ending. Don't give the Reaper baby to TIM and take his research on it, no control. Rather than an arbitrary number deciding these things, actual choices deciding these things would have a much bigger impact - not everyone would almost always have all choices unlocked ['cause god damn is that easy to do, especially with multiplayer], which would make actually unlocking a choice more unique, and more personal if done right [I.E: Agreeing with TIM to control the Reapers is what leads to the control ending, not disagreeing, disagreeing, disagreeing, oh look, I can control] - and also changes things based on your choices. This would be slightly unpopular, as people who made poor choices previously would have to play the whole series again to fix them, but personally I think that was part of what people wanted, and why people had a lot of saves with different play styles prepared to play 3 with. Plus, replayability is never a bad thing.
Another thing that could be done, but doesn't directly reference the main choices, is extending the intro on Earth. Giving you some free roaming and pre-trial time, rather than trying to control the story and just get you off Earth ASAP because we want to start the space kid stuff. Allow you to roam around Earth, and meet some of the people you'd interacted with previously. Find out what Giana parassini is up to [How do you spell her name again?], meet Commander Kirahe if you saved him, and here how he'll vouch for you in your trial. Speak to Anderson and Udina, and see how your choice of councillor changes their attitudes. Talk to that Asari who was saved by the Rachni, and hear how they're doing. It works as good foreshadowing for the rest of the game, gives you a quick reminder on which choices you made, and also gives you a bit of recognition for your choices, which always feels good.
Its not hard to make choices matter. Its more that Bioware didn't want to, or didn't have the time to.