A sentence which begins with a preposition, like yours, is perfectly correct, and it would be inaccurate to characterize it as sounding artificial. Your sentence as written is not wrong, and one reasonable interpretation of your sentence is exactly what you intended to say. It is not the way most native English speakers would express this particular thought, but in literature and formal writing you will find many beautifully-composed sentences which begin with On. To cite just a few:
On my volcano grows the grass,—
A meditative spot,
An area for a bird to choose
Would be the general thought.
On the Mountains of the Prairie,
On the great Red Pipe-stone Quarry,
Gitche Manito, the mighty,
He the Master of Life, descending,
On the red crags of the quarry
Stood erect, and called the nations,
Called the tribes of men together.
On the beach at night alone,
As the old mother sways her to and fro, singing her husky song,
As I watch the bright stars shining—I think a thought of the clef of the universes, and of the future.
These examples illustrate the way in which a sentence beginning with On may be perceived, and that may be part of the reason why your first sentence strikes some native English speakers as mildly humorous: the juxtaposition of a form which brings to mind poetic expression with such prosaic things as a horse and wallpaper seems incongruous, especially before we learn that the wallpaper here is a background image on an electronic screen.
Below is one example of the image your sentence might conjure in the mind of the reader:

Because the preposition on can mean so many things in English, your sentence lends itself to an interpretation which brings to mind a humorous image. It is sometimes important to express a thought carefully in order to avoid unintentional Ambiguity; as some of the commentary to your question indicates, this is a fertile source of humor.
There are many ways in which your sentence might be interpreted. If you wish to describe a background image (sometimes referred to as wallpaper) for use on a computer or handheld device, you might say:
- The background image pictures a horse.
- The wallpaper* image shows a horse.
- On the computer wallpaper is a picture of a horse.
- There is a picture of a horse on the wallpaper*.
* This could denote any kind of wallpaper, even the kind we put on walls.