Thought this would be a fun one to work on:

Wikipedia informs me that on a level plain, a 5 foot 7 inch person (neighborhood of 1.75 meters) sees the horizon 3 miles away.
But what if you're on my Underland and the "earth" on which you stand has only half the radius, or less, than the "Earth?" A smaller ball should mean a farther horizon, methinks, but I'm not sure.

EDIT:
Believe it or not, some people on the internet already did this.
These articles will be of use to you if you want to plan how far away objects are to your characters' vision, or if you have planets with smaller or larger radii.
The effect of different radii
Table of distances for earth-sized planets

Interesting!

I was wondering just yesterday about the converse: what if you're in a world that, like Narnia, is a plane rather than a sphere?

The point of a palpably different horizon also comes up in Niven's Ringworld and at least the first sequel (I haven't read any further than that ...); the Ringworld is so large that it includes life-size replicas of every inhabited planet of "Known Space," but instead of curving down as on a sphere, the horizon curves up.

And there's also a less-well-known science fiction novel I've read (which I hesitate somewhat to recommend due to "language" and "content" issues, but here's a link to it on Goodreads) in which the main "other world" is significantly larger than Earth, but what really messes with the character's "horizon sense" is that it's a binary planet, with a "moon" that covers (if I remember correctly) up to about a quarter of the sky.

Slight tangent: The best visual example I've ever seen of a ringworld horizon is, of course, in the Halo series. See here:
http://i.imgur.com/pDLPvFj.jpg

To me, that looks like a normal horizon with the ringworld arch added to the background, not a horizon that slopes up instead of down ...