Ahhhh... Aristotle's wheel. How you have confounded us for so long! I mean just look as this animation, something must be misleading here. And oh there is. Let us examine three different cases/views of this animation to shed light on this mystery.
1. Examine how the different points on the wheel move around: obviously by inspection the different points are unfurling at different rates. Also to mention, every point along the radial line have the same angular frequency, also called angular velocity (ω). This means that all the points on the radial line rotate around in a circle at the same rate (same revolutions/second.) However they are moving at different linear velocities. This must be true since points lying farther out have a larger distance to travel around (larger circumference) and therefore must move faster in order to go around in the same time. So, if they have move at different linear speeds within the same time, they cannot possibly have traveled the same arc length, and hence circumference. (Note that arc length s=rθ , and ω=Δθ/Δt so if ω and Δt are the same for both, Δθ is the same for both. This means that since they both have different radii r, they cannot rotated the same arc length s. Furthermore, since v=Δs/Δt , having the same Δt and different velocities v implies that the wheels will again travel different arc lengths.)
2. Zero Radius.
Consider the central point of the circle. Is it rotating? Angular mechanics dictate that the tangential velocity of a point on a circle (in the specific case of rolling without slipping) to be
However the central point has a radius of zero so this mean that it has a tangential velocity of zero and therefore does not rotate. Similarly this point will trace out a circumference of zero as it moves. Yet this point is still displaced exactly as far as a point of any other radius. By inspection we notice points of any radius are all displaced the same. So this must mean that rotation does not have anything to do with horizontal displacement; every point of the radial line is on the same footing regardless of circumference.
Consider the case whether the center of the wheel is fixed (think a wheel suspended that's spun by a hand.) In one revolution of the wheel, what is the displacement of the points on the radial line? Zero. They go back to the same point they were before. Wheel motion is simply this case plus some horizontal displacement.
The "proof for this contradiction is simple.
Assume since that two wheels are rigidly connect with respective radii of r and r' (where r ≠ r') so that they have the same angular velocity ω. For both wheels to travel the same horizontal distance Δd they must have a velocity (v=Δd/Δt) and time (Δt) so that vΔt =v'Δt'. Both wheels having the same ω implies directly that they will have the same period T (time to go around one revolution.) This comes from T=1/f= 2π/ω, where f is frequency. So this means that Δt =Δt'. Assuming that both wheels are rolling without slipping, v=rω and v'=r'ω. But since r ≠ r' , v ≠ v', so therefore vΔt ≠v'Δt' which is a contradiction. We conclude then that both wheels cannot be rolling without slipping.
But what does this mean for the larger problem?
Well for starters, this means that least one wheel is definitely not tracing out its circumference. This matches our intuition about the animation where clearly the wheels seems to be "unraveling" at different rates, where if both traced out their circumference we should see no difference since they complete this task in the same time. If both circles cannot simultaneously trace out their circumference we should see no problem that they can both travel the same horizontal distances despite their different circumferences.
To end, we should clarify the physical difference between rolling without slipping and rolling with some slipping. After all, those from Michigan can attest to driving while slipping on ice/snow. When this occurs, some slipping between the ice and tires is occurring, which causes the wheel to slide on the ice and make the driver lose control (this is because the force changes from static friction to kinetic friction, link to a good explanation here.) Another example of rolling with slipping is getting your car stuck in gravel/dirt/snow. The tires will just rotate indefinitely without catching. Obviously they are not traveling their circumference (the car isn't moving forward!)
So for the example with the tire, replace both wheels with metal tires and drive over sandpaper. Although the larger wheel may get indents because of the unevenness of the sandpaper, the smaller wheel will be covered in scratch marks which indicates that it is "dragging" or "slipping." If you don't believe me, build and test it!