If I wanted to get a really clean colored background like here, what kind of material should I use for the backdrop? My first instinct would be paper, but matte has a very slight texture and glossy paper is, well, glossy.
Paper can work. I've done a few shots with a roll of butcher's paper as the backdrop. As you note though, there are many different types of paper and some have a more pronounced texture than others.
There are papers specifically designed for this - For example on Amazon Savage Seamless Background Paper, 53" wide x 12 yards, Super White, #1... and there is a whole color set on them.
On B&H there is an entire category for seamless paper.
There's also muslin or fabric, canvas, vinyl, and pvc that is sometimes used - for different effects (the fabric ones are often used with scenes or abstract patterns painted on them).
Paper has the nice bit to it that its cheap and after someone with dirty shoes stands on it, you can just cut off that bit and roll a bit more out.