I have seen pictures of World War I-era airplanes that have rudders much smaller than today. When did the first rudder come out?
Planes as early as the wright glider (1902) had a rudder, it appears from pictures that the 1900 and 1901 variants did not have rudders but its hard to tell from the photos.
Depending on your definition if you are talking about powered flight the Wright Flyer (1903) had 2 rudders much like its earlier glider predecessor.
In the lighter than air category, the Giffard Dirigible (1852) had a sail like rudder in the aft of the ship. So that may take the cake if you have consider it a true rudder.
Side Note: Patented in 1930 the V-Tail design could be argued as the first design that did not (as far as I know) employ a rudder. The earlier Beechcraft Bonanza's are the most common plane of that design in commercial production. There is quite a bit of debate as to the safety of ruddervators and the general theme seems to be that they are not perfect and do require some care to fly properly.
1785, when Jean-Pierre Blanchard
crossed the English Channel in a balloon equipped with flapping wings for propulsion and a birdlike tail for steering
according to pages 26-27 of L. Winter and G. Denger's "Minute Epics of Flight," published 1933.
We don't have photos, but we do have a woodcut.
Rudder itself was used before the Wright. It was just the idea of a rudder on a boat. Otto Lilienthal flew a glider which had a tail with a modern look in 1894:
Actually the whole airplane has a modern look, like the cambered wing, Lilienthal was an aerodynamicist, he invented the polar curve.
Note: The rudder is not meant to control the aircraft direction --this is done by rolling the wing,-- but to counteract the adverse yaw which develops when the wing is rolled (more drag on the upper half of the wing). This effect can be obtained even with a fixed rudder (the turn will not be coordinated, but this tends to prevent a spiral dive).
So the size of the rudder is proportional to this force, which is smaller on small wings.
The 1785 balloon answer is interesting. However, we might note that flapping wings would be extremely ineffective at propelling a balloon, and a rudder will have no significant effect on a free (unpropelled) balloon. With that in mind, we might conclude that George Cayley was the first to suggest the use of a rudder in a practical way on an aircraft.
In 1799 George Cayley inscribed a coin with a picture of a design for a glider that appears to include a movable rudder. By 1804 he had built a flying model glider that included a cruciform tail that could be adjusted on the ground both in the pitch and yaw dimensions. By 1848 he had created an illustration of a full-scale glider that included a similar tail that could be adjusted in flight. He tested a full-scale glider built along these lines in 1849, and a larger similar glider in 1853.
Here is one link that covers Cayley's work: http://www.flyingmachines.org/cayl.html
More recently, the Wright brothers first used a moveable rudder on their 1902 glider, and also used one on their famous 1903 airplane, generally recognized as the first airplane capable of sustained, controlled flight.
Having said all that, I wouldn't be surprised if someone located an earlier example of a rudder in a drawing or even an operational (small) model airplane or glider. It is a fairly intuitive concept, deriving directly from naval technology-- in fact, the naval precedents might well have tended to lead early inventors to overestimate the advantages and results of having a movable rudder on an airplane.