Go with the 25s. You'll notice more of a difference and you still have bikes with thicker tires. When I first started biking, my 23s looked very skinny to. I've grown to like them.