Memory is how much memory PHP gets to handle uploads. In THIS instance, what you are seeing on Add Media is 100% unrelated. Put it aside for now :)
That 10MB on Add Media directly relates to how big a file PHP allows. That's set via upload_max_filesize in PHP, and yes, yours is 100M but that's not picking up, which MAY mean there's an issue with permissions and how your server allows that.
Who's your webhost? Have you asked them how to change that?
This guy is suggesting I modify something in the database, but it seems to me like that should be the value that is changed on the Network Settings page in the Dashboard.
That guy is wrong :) You have already made the needed change on /wp-admin/network/settings.php
The odds are it's a quirk of your webhost.