Not a linux user, but a decent external mic or headset is going to make the most difference here, its largely a factor of the tiny internal mics in laptops. They will also do better with sound insulation, internal are not well insulated from the fan, keyboard etc.
Tone changes can help with audibility. I have a really low voice, it doesn't carry well over voice-chat; I'd push my register up a few notes. But yes, filtering tweety mic sounds from other people would be good too.
