What was it about the histories, missions, and leaders of the Northern Army and Navy that lead them to handle this issue quite differently?
You have a slight error in the assumption you are making here. While you are correct with regards to the Segregationist aspect - the Union Army having African-Americans serve in the USCTs while the Navy saw black sailors as part of mixed-race ships crews - I can't say that I agree with you on the numbers, as both services actually had, proportionally, not dissimilar levels of black participation. The difference lies entirely in the history, since, while not allowed into the roll of officers, black sailors were allowed to serve in the US Navy throughout the 1800s, although before the war, by regulation the black complement of a ships' crew was not supposed to be more than 1/20th of the whole, although this was not always followed. During the War of 1812, the Navy was nearly 1/6th black! To be sure, black sailors were more likely to be lower in the ranks, and it would be more common to see one working in the mess than working a gun crew, but you could find black men in both roles during the period. It wouldn't be until the early 20th century, in fact, that the Navy's policy became openly segregationist, and while a limited number of black sailors continued to serve on ship, with almost no exceptions, they were restricted to menial labor.
In the Army however, while African-Americans had served in the ranks during the earliest days, fighting with distinction in the War of 1812 and the Revolution, by the dawn of the Civil War, it was essentially a 'Whites Only" institution, and although a limited number of volunteer units were raised early on, it wasn't until early 1863 that the decision was made to make full use of the free black population as soldiers, but they remained in segregated units - the United States Colored Troops - led almost exclusively by white officers.
So while on the one hand, there are simply practical reasons to explain the different approach - raising and training an all-black enlisted regiment is easier than raising and training an all-black enlisted ships' crew, as it is easier to teach men to soldier than to sail - really, the difference is historical, as the Navy had a long and essentially unbroken history of black involvement in its ranks, while the Army's history there was much less notable. In both cases though, by the end of the Civil War, African-Americans were serving in large numbers. With 10,000 or so black sailors, and roughly 180,000 black soldiers, at 11.8 percent and 8.5 percent or so of their respective services total numbers (total numbers being 84,415 in the Navy and 2,128,948 in the Army).
Sources (Some PDF warnings):
Freedom by the Sword: The U.S. Colored Troops, 1862-1867 by William Dobak - Solid (and free!) resource on the history of the USCT.
The integration of the Negro into the United States Navy, 1776-1947 by Dennis Nelson - Not so solid resource on history of African-Americans in the Navy, but it is a less traveled topic than the Army for the Civil War period.
Letter from the Secretary of the Navy to Cognress, August 10, 1842
American War and Military Operations Casualties: Lists and Statistics by Nese F. DeBruyne and Anne Leland