I've been playing for hours and hours and I'm on my third system. I've found fucktons of ship upgrades, Exosuit expansions & a few upgrades, & Multitool upgrades...but I don't have any space for these upgrades because I'm still using the default Multitool.

I've read that Multitools are located in buildings that have aliens in them. I've found a bunch of these buildings and talked to the aliens but I've never seen a new Multitool. Do I have to travel further into the galaxy?

Sometimes they are in little cases on the walls to buy or aliens will give you one. They should be everywhere no need to travel.

If I remember correctly I mostly encountered them while doing find transmission missions on the orange radar beacons

Look at the panels on the walls. They`re usually in there. Not all the time but sometimes. Could be just the luck of the draw in your case.
Don`t expect anything amazing though, you may get 1 extra slot!

I like mine because it looked a lot better than the default yellowy one which is made for girls. But it only allows one extra slot.

Yeah, I just looked at another one in a building, but it wasn't as good as the one I built up. It's my 3rd Mutlitool, as I go someday there will be one with a ton of slots that I can't refuse. They are on the wall in a show case, just go up to it and press E to examine it.

Probably random, but people you meet in the colonial bases tend to want to trade you their multitool if you have high enough standing. Or give you a better one sometimes (only happened with the Vy'keen with the highest standing so far). Otherwise, the shelters and the bases can have new ones on the walls.

A monolith event rewarded me with one one time too. Funkiest design so far. Really like the writing for those events..

I got mine from a guy who basically barked at me, "Hey, hand me your weapon!" so I did, and he gave me a much better one. I've seen them on display shelves as well though.

I don't remember where it was (not that it helps), or the alien race name but they considered themselves Warriors..But I think it was on the second system I went to.

I haven't seen any display cases yet. I don't care if I find one that only has one more inventory spot. Anything's better than what I have now. Guess I'll keep on looking.

I think your standing with them affects the chances of then giving you new multitools. It increases quite fast though.

I'm pretty sure I'm maxed out with them by now. I never have to mine for carbon anymore because they keep giving it to me when I talk to them :P