A major clearly outranks a lieutenant. So, why then does a “Lieutenant General” have 3 stars and a “Major General” only 2 stars? How is that not backwards?
From Wiki.
It helps to think of it like this: there are company grade (O-1 through O-3), field grade (O-4 through O-6) and general officers (O-7+) by statute. Excluding brigadier generals, which are an aberration of history, that means that you have Captains, Colonels, Generals, and their help.
Captain <- head of company
Lieutenant [Captain] (1st & 2nd) <- assist the Captain
Sergeant Major [Captain] (enlisted rank) <- the muscle
Colonel <- head of regiment
Lieutenant Colonel <- assist the Colonel
[Sergeant] Major [Colonel] <- the muscle
General <- head of numbered army
Lieutenant General <- assist the General
[Sergeant] Major General <- the muscle
Makes sense. ISTM General = [Captain] General in this context
Like **steronz **said, they’re basically historical artifacts. Here’s a bit more etymology…
So a “Captain” is the head of a company of soldiers (Captain derives from “caput”, latin for ‘head’).
Colonels are the head of a column, which in the late medieval period, meant a group of companies.
Generals are actually short for “Captain-General”, which meant a sort of commander-in-chief of a field army in the late medieval era- a Captain with broader responsibilities for the entire army, in other words. We see this sort of usage in terms like 'Inspector-General", “Surgeon-General”, “Solicitor-General”, “Postmaster-General”, etc…
Lieutenant derives from French - in essence it means “tenant in lieu of <a specific superior>” or a placeholder/second-in-command. So lieutenants are the placeholder/second-in-command for captains, lieutenant colonels are lieutenants for colonels, and lieutenant generals are lieutenants for the captains general.
One nitpick with steronz’ post
Captain
Lieutenant
Sergeant
Colonel
Lieutenant Colonel
Sergeant Major
Captain General aka Colonel General aka General
Lieutenant General
Sergeant Major General
The Sergeant Major’s functions got split up.
The “leadership” functions went to the Major, who became a mid-level commissioned officer, commanding a battalion.
The “responsibility” functions went to the Sergeant Major, who became the senior NCO. The responsibilities also got divided between the Company Sergeant Major and the Regimental Sergeant Major (which are usually job titles rather than rank titles).
This explains a little. I have seen this myself in the National Archives.
You didn’t ask, but in the Navy, you originally had just two officer ranks: Captains and Lieutenants (and Midshipmen, who were officer trainees). The Captain was in charge of the whole ship (and a given ship only had one captain). Lieutenants (might be several) were their assistants.
However, as ship technology developed, you ended up with a wide range of ship sizes, from small patrol craft manned by a few sailors (like JFK’s PT-109) to battleships and aircraft carriers manned by thousands of sailors. Whereas a typical ship captain in theAge of Sail might command a few hundred sailors (similar in size of an Army company), a Navy Captain commanding a battleship with 2,000 or more sailors is clearly in a different category. Instead, they are more akin to a Colonel, who commands a regiment. So ultimately, the rank of Navy Captain was made equivalent to that of an Army Colonel.
In the meantime, the smaller vessels were now being commanded by Navy Lieutenants (and a Navy Lieutenant ultimately became equivalent to an Army captain – confused yet?). 
The Navy lieutenants who were actually in command of a vessel wanted to distinguish themselves from the ones who were just assistants, and so called themselves “Lieutenants, Commanding” which ultimately turned into the Lieutenant Commander rank. The Lieutenant Commander rank is now equivalent to a Major.
Later on, when it became desirable to line up all of the ranks between the services (from O-1 to O-10), they Navy had some gaps in their ranks, so a rank was added between the Lieutenant Commander rank and Captain rank, which naturally became the Commander rank (now equivalent to a Lieutenant Colonel).
Today, very small vessels (like a patrol boat) might be commanded by a Lieutenant. A minesweeper might be commanded by a Lieutenant Commander. Destroyers, cruisers, and submarines are typically commanded by Commanders, and Aircraft Carriers are commanded by Captains.
Another historical oddity is the names of the ranks for one- and two-star admirals. Both are called “Rear Admirals,” which is confusing. Back in the '80s, they tried to rename the one-star admirals as “Commodores”, but they didn’t like not being in the admiral club, so that didn’t last long. The two ranks are now distinguished as “Rear Admiral - Lower Half” and “Rear Admiral - Upper Half,” which comes from the old promotion lists (i.e. “top half” of the list vs. “bottom half” of the list).
This was sort of alluded to by bump already, and I’m sure it’s mentioned in one or more of the various links already given in this thread, but just to lay it all out here too: “General” nowadays is of course a noun: The Pentagon meeting included five generals, three colonels, and a captain (who was tasked with getting everyone’s coffee). “Generals” in this sort of context will often include people with various ranks from brigadier general on up to a “full” general (four stars) or, in theory, a five-star general (General of the Army in American usage).
But the “general” in “lieutenant general” was originally an adjective (what’s called a “postpositive” adjective, coming after the noun it modifies instead of in front of it, which is unusual for English, though normal in many other languages). So, for a small group of soldiers–a “company”–you would have the “captain” (literally the “head” of the company) assisted by one or more “lieutenants” (which just means “deputy”; literally, “a placeholder”). For a large group of soldiers (an “army”) you would have the “captain general”, which originally would be understood as the equivalent, in standard modern English, of the phrase “general captain”–the captain (head) of the whole shooting match. He would be assisted by one or more “lieutenants general” (that is, “general lieutenants”). As already noted, “captain general” eventually got shortened to just “general” (although the older title is still used in various contexts, but mostly not in regular non-ceremonial usage in English-speaking countries), and “lieutenant general” went from being understood as a very fancy form of a “lieutenant” (or deputy) to being one of several ranks of a “general” (or “general officer”). And the more usual modern plural would be “lieutenant generals” instead of “lieutenants general”.
Warrant Officers?
Flying Officers?
It’s a bit more complicated.
What is the command relationship on a ship when, say, an admiral uses it as his flagship? Does the ship’s captain just bite his lip? I guess he has to. That might be a tad grating if there’s disagreement.
Of course it is. Isn’t that always the case? 
BTW, your links are broken. Corrected links:
Generally the admiral will be busy overseeing the overall strategy for the fleet (carrier group, whatever) and the flagship’s captain will be busy overseeing the actual operation of the ship. Obviously the captain will be taking orders from the admiral, but it’s not much different from taking orders from an admiral from afar. On a large enough flagship the admiral and their staff will have their own admiral’s bridge and meeting rooms.
This might come up when you have something like a carrier strike group (CSG), which is typically commanded by a 1-star admiral. In this case, the admiral has the same relationship with the captain of the ship on which he resides as he does with all of the commanding officers (COs) of the various units making up the strike group. It makes no difference that the admiral happens to be physically present on the flagship. All of the COs of the various units in the strike group are under the command of the admiral, so all orders from the admiral go through the COs of the individual units in the group, including that of the flagship.
As far as the flagship itself is concerned, this means is that the CO of the ship is still the commanding officer. He doesn’t “bite his lip.” He commands his ship, and follows the orders of the admiral in charge of the entire group. So any disagreement between the CO of the flagship and the admiral is handled like any other command relationship.
With that said, the Navy takes the position of ship captain very seriously. We had the Chief of Naval Operations (CNO) aboard my submarine once. He’s the 4-star admiral in charge of the entire U.S. Navy. When we sat down to dinner, he did NOT take the captain’s spot at the head of the table. He sat to the captain’s right as the guest of honor. For sleeping assignments, the admiral did not bump the captain out of his personal cabin; instead he shared a stateroom with the Executive Officer (second-in-command).
Incidentally, if the CO was not present at a meal, nobody else sat in his chair, not even visiting admirals.
The admiral is telling each of the captains what actions he wants done. He shouldn’t be interfering with how any of the captains get their job done (who he assigns to particular jobs, etc.). The same applies to the captain of the ship that the admiral is actually on. Giving direct orders to (say) a tactical officer on the flagship would be a faux pas - he tells the captain and the captain tells the tactical officer. The admiral should be working with his personal staff (not part of the ship’s complement) on the big picture issues anyway.
I guess my “bite his lip” comment was because in my mind I was thinking about Lindemann and Lütjens on the Bismarck. From my meager knowledge of things, sounds like they had major tactical disagreements but that may have been unique to them, the German Navy, or just the fact that the Bismarck was unique…
Want to have more fun trying to wrap your mind around ranks? In the United States, Chief Warrant Officers (W-2 through W-5) are commissioned. It is only the Warrant Officer (W-1) that receives a warrant instead of a commission.
In other countries, the Warrant Officer is the senior enlisted position and that country may have one or two Warrant Officer ranks.
In other countries, there may be one Warrant Officer rank for one service, but two for another service.
One of the unique factors might have been the fact that the task force that Lütjens commanded consisted of just two ships, the battleship Bismarck and the heavy cruiser Prinz Eugen, and at some point before the final engagement that sank the Bismarck, the two ships were separated. So you then had an admiral in charge of a single-ship “task force” consisting of only the flagship.