Q: My almost-new computer is already full. Memory says "other," but movies, pictures and downloads are not responsible. Trash is empty. Help?

https://support.apple.com/en-us/HT201716Reindex spotlight and post a picture here. Also do some house cleaning.   https://support.apple.com/en-us/HT201716

The warranty entitles you to complimentary phone support for the first 90 days of ownership.

Before you call AppleCare or head out for an Apple store, try this. Restart the computer and as soon as you hear the chime, hold down the Shift key. Once the Apple menu has appeared you may release it. This is called Safe Mode and during the safe boot two important things happen: temporary files are deleted/trimmed and the hard drive directory is repaired. Once the computer finishes booting, restart again as normal.

Check your free drive space again - ignore the bar, just look at free space. Does it look more reasonable? I have no idea what you have on your hard drive so I can’t say how much should be free but a new computer with a 128GB drive should have something like 100GB free. If this worked, the reason it worked is that sometimes a temporary file that should have been erased or trimmed isn’t. When that happens the problem tends to cascade.

If numbers look right you can try reindexing again. Spotlight: How to re-index folders or volumes - Apple Support Spotlight indexing has been problematic for as long as I can recall and I basically ignore the bar graph as basically useless. When the index becomes confused Other gets larger and larger as files that a pictures or programs get counted under the Other category and not the one they belong in.

To see what the hard drive looks like in relation to files and free space. Go to the hard drive on the desktop and right click on it then (get info). It will give you capacity- available and used. If this does not agree with the systems report then spotlight is not indexed right. Hard drives should never be more than 90% full. This means a 128Gig drive should have at least 12 Gig's of free space. If it gets too full then your Macbook Air will become slow and maybe even unresponsive. You can clean out log files cache files and history files Not the file header themselves, but what is in them. You can also go to the update folder in your main library and delete the updates except the product metadata plist and index plist.In Itunes you can open it and at the top click view and show duplicates and delete any. If you have deleted programs you installed and did not have an uninstaller for them(Which is the best way to uninstall) then you will need to do some research as to what other files came with it  and manually delete them. If you can not do this from a normal startup, Use safe mode. Which is Shift key at startup.  If this is still giving you problems, take Link's advise and use your complementary  90 day free tech support.

Just so you know what OTHER represents, please read this:

https://support.apple.com/en-us/HT202867

The category itself is NOT the problem.

Ciao.