I'd like to know why F-Droid shows updates before Google Play Store. Wouldn't the developers of such apps submit changes at the same time to both?
It's common for app developers to upload their updates to many markets at the same time; certainly they want as many users as possible to use their latest update. The only difference is how quick their updates are up on each store. Since F-Droid update workflow is considerably simpler than Play Store (automatic build from source, and no further server validation), big chance the apps will be up on there first.
While I have never used F-Droid, market apps in general can check updates for already-installed apps by getting and comparing their package names and versions, even though if it's installed from different source. (That's already possible by comparing 3rd-party apps manager: show app's package name and version from its manifest).
F-Droid also tells me that the signing key is different as well. Is it a common practice to create new signing keys upon updating an app?
From this statement, I assume you installed the apps originally from Play Store, then F-Droid notified you about the update.
First, I think there's a little misunderstanding: it's uncommon to create new signing keys upon updating an app, because it prevents users to update it!
The more reasonable practice is, that the developers use different keys for each store, but still (and must) use the same key when updating their apps to particular store. This might be used to prevent cross-market to interfere the update (e.g. security issue, different flavor, etc).
The other reason (which is this case) is, F-Droid forces their apps to be signed by them:
Packages built by F-Droid are signed by F-Droid, so all apps in the official F-Droid repo are signed by F-Droid keys. F-Droid will generate a new key for each app that is included. All of the different APKs built from different versions of an app will be signed by the same app key. But do note: if an app is also distributed in an APK signed by the developer, like in the Google Play Store, then the F-Droid APK will have a different signature.