Most of the Missouri between Sioux City and the Fort Randall Dam (the next one upstream from Gavins Point) forms the Missouri National Recreational River. The website for the MNRR implies that shallow-draft boats can navigate in this stretch of river, but it’s tricky.
You can definitely motorboat from Sioux City to Gavins Point Dam, you are going to want to be planing and watching for snags and sandbars, but it is absolutely possible. Source: I’ve drifted down from Gavins Point to Sioux City several times. However, I think you could get further inland than Gavins Point dam by canoeing up the Big Sioux River or up the Jim (James) River. I’m not very familiar with the Big Sioux River and I know that getting through the Falls in Sioux Falls is going to require a portage. But I know that you could powerboat to highway 81 north of Yankton and paddle easily to Olivet, SD and in some years paddling up to and past Mitchell would be possible (not fun but possible).
So I put forward Olivet, SD as the furthest inland one could get solely on a boat up the Missouri River route.
And now I found a blog which goes from Mitchell (not down to Olivet but the river looks to be substantial enough). Just watch out for cows in the water (not joking).
You can certainly navigate the Missouri via recreational power boat at its headwaters and somewhat above in the three tributaries (which are also unchannelized), and it’d be surprising if it were less navigable anywhere below that.
I stand corrected (by several of you) – for most purposes, especially historically, Sioux, City, Iowa is the head of navigation on the Missouri, the functional equivalent of St. Paul, Minnesota. Sioux City is a bout a hundred miles upstream from Omaha.
(Omaha grew into a city mainly due to its proximity to where the Missouri and Platte Rivers meet – the Platte valley has been an important overland route to the west since the Oregon Trail days).