First to get more than 1 million votes: William Henry Harrison and Martin Van Buren in 1840.
First to get more than 2 million votes: Abraham Lincoln in 1864. He won 55% of the total vote in this wartime election. (In his first election, before the South seceded, he won less than 40%, although it was still more than 10% more than the nearest opponent.)
First to get more than 3 million votes: Ulysses S. Grant in 1868. Grant won 55.6% of the popular vote, more than any candidate since Andrew Jackson in 1828.
First to get more than 4 million votes: Rutherford B. Hayes and Samuel J. Tlden in 1876. Famously (or infamously), Tilden got more votes, the election hinged on Florida and was decided by a commission along partisan lines.
First to get more than 5 million votes: Benjamin Harrison and Grover Cleveland in 1888. Cleveland got more votes, but Harrison prevailed in the Electoral College. That didn't happen again until 2000.
First to get more than 7 million votes: William McKinley in 1896. McKinley was the first candidate to get more than 50% of the vote since Tilden in 1976 and first to win with more than 50% since Grant in 1872. William Jennings Bryan won over 6 million votes, more than any candidate before that year.
First to win by a margin of more than 1 million votes: Teddy Roosevelt in 1904. His margin was actually over 2 million votes, and his percentage (56.4%) was more than anyone's since Monroe ran unopposed in 1820. (Interestingly, his Electoral College victory was not particularly lopsided: he won 32 out of 45 states and 70% of the electoral vote. He was, however, the first candidate to win over 300 electoral votes.)
First to get more than 10 million votes: Warren G. Harding in 1920. Harding was also the first to get more than 15 million (actually more than 16 million), the first to win by a margin exceeding 5 million (actually over 7 million) and the first to win more than 60% of the popular vote in 100 years, since Monroe in 1820 (and first to do that in a competitive race since 1808). It is interesting how little relation there was between his electoral success and his record as President. He must not have been unpopular in his time, though: when his successor Calvin Coolidge ran for reelection, he won by a popular-vote margin of 25.2%.
First to get more than 20 million votes: Herbert Hoover in 1928. Hoover also set the new record with 444 electoral votes. His opponent, Alfred E. Smith, became the first losing candidate with more than 10 million votes.
Franklin D. Roosevelt set the new popular-vote record in 1932, although without crossing any trivia-worthy milestone. However, his popular-vote percentage (57.4%) was the highest for a Democrat since Andrew Jackson. Moreover, he was the first Democrat to get more than 50% of the vote since Tilden in 1876 (neither Cleveland nor Wilson ever accomplished that) and the first Democrat to win with more than 50% of popular votes since Pierce in 1852.
First to get more than 25 million votes, and first to win by a margin of more than 10 million votes: FDR in 1936. (Only LBJ in 1964, Nixon in 1972 and Reagan in 1984 have won by more than 10 million votes since.) His 27.7 million votes was not surpassed until 1952. FDR also bested Harding's modern-era record in popular-vote percentage (60.8% vs. 60.3%). His 523 electoral votes remained the record until 1984 and is still the record percentage-wise (2 states have been added to the Union and DC has become represented in the Electoral College since then).
FDR was also the first candidate to win a cumulative total of over 100 million votes. In his 4 presidential elections, he won a total of 103 million votes.
First to lose despite getting more than 20 million votes: Wendell Wilkie in 1940.
First to get more than 30 million votes: Dwight Eisenhower in 1952. In his 1956 reelection, Eisenhower got over 35 million votes, and won more states (41) and electoral votes (457) than any Republican before him.
First to lose despite getting more than 30 million votes: Richard Nixon in 1960. Nixon was also the first loser to get more votes than FDR got in any single election.
Popular-vote records set by Lyndon B. Johnson in 1964: first to get over 40 million (43.1 million), highest modern-time percentage (61.1%), first to win by a margin of more than 15 million. It was also the first time Vermont voted for a Democrat since 1852 and the only time ever Alaska did so, but also the first time ever that Georgia voted for a Republican (which it didn't do even during Reconstruction).
First to get more than 45 million votes: Richard Nixon in 1972. In his 3 presidential elections, Nixon won a cumulative total of 113 million votes, breaking FDR's record. Nixon's cumulative vote record still stands.
First to get more than 50 million votes: Ronald Reagan in 1984.
Reagan is the most recent president who won more than 50% of the vote twice. That is a surprisingly rare feat; the only presidents who accomplished that before Reagan were Eisenhower, FDR, McKinley, Grant, Jackson, Monroe, Madison, Jefferson, and Washington. Note that the list includes 3 Founding Fathers, one who essentially ran unopposed (Monroe), three generals famous for critical victories in major wars (Jackson, Grant, Eisenhower) and only 3 "normal" politicians (McKinley, FDR, Reagan). Of the 5 candidates on the list whose popular vote counts are reasonably meaningful (that would be starting with Grant), FDR had the highest average vote percentage (56.6%), followed by Eisenhower (56.3%), Reagan (54.8%), Grant (54.2%), and McKinley (51.3%).
First to lose despite getting more than 40 million votes: Michael Dukakis in 1988.
Bill Clinton was the first president since Wilson to win twice with less than 50% of the popular vote. That is an even rarer feat than winning twice with over 50%; only 3 candidates ever did it. (The third, or chronologically the first, was Grover Cleveland.)
First to lose despite getting more than 50 million votes: Al Gore in 2000. Of course, Al Gore lost only because the votes in Florida were not properly counted.
First to get more than 60 million votes: George W. Bush in 2004. Bush thus joined FDR and Nixon as only the third person to get more than 100 million cumulative votes. He failed to best Nixon's record, but he did win the most votes in 2 elections. (Nixon's cumulative votes are a 3-election total, and FDR's are over 4 elections.)
Will Obama exceed 70 million? With a good turnout, that is possible.
Honorable mention list: John Kerry (2004), James M. Cox (1920), Charles Hughes (1916), William Jennings Bryan (1896), Grover Cleveland (1888), James Blaine (1884), Winfield Scott Hancock (1880), Samuel J. Tilden (1876), Horatio Seymour (1868), Winfield Scott (1852), Henry Clay (1844), Martin Van Buren (1840), John Q. Adams (1828), Andrew Jackson (1824), DeWitt Clinton (1812), and Thomas Jefferson (1796) lost, but got more votes that anyone before them. Cleveland, Tilden and Jackson also got more votes than the winner of their election. (Note that John Adams in 1800, Charles Pinckney in 1804, Horace Greeley in 1872, Benjamin Harrison in 1892, William Jennings Bryan in 1900, Herbert Hoover in 1932, Wendell Wilkie in 1940, and Thomas Dewey in 1948 also got more votes than anyone other than themselves or the winner of their election.)