It doesn't matter whether you install the media pack before or after the patch, although I recommend installing it before the patch as a matter of principle (because that way if updated media pack files were to one day be released as part of a patch, you would already be in the habit of installing in the correct order).
If you install FfH2 and Patch O, but you find that FfH2 will run under 3.17 and not under 3.19 then you've done something wrong. You may be using the wrong install files, or installing them in the wrong place. I suggest that you delete your "Fall from Heaven 2" folder, delete the installers and patchers that you have downloaded, and then make sure that Civ 4 is installed and patched correctly and working.
To do this, load Civ 4 and at the main menu select "ADVANCED" and then "ABOUT THIS BUILD". The line "Build Version" should read "3.1.9.0 (128100)". If yours does not match this, then you'll need to get Civ 4 + BtS installed and patched correctly before you proceed. I recommend installing Civ 4 + BtS + 3.19 patch. It should not be necessary to patch Civ 4 before installing BtS, and it should not be necessary to install patch 3.17 before installing patch 3.19.
Once Civ 4 + BtS v3.19 is working, you should download the FfH2 installer (called "2009_05_16_FallfromHeaven2041n.exe") and the FfH2 Patch O patcher (called "FfH2041o.exe") from the links in the first post of the
FfH2 Bug Thread. (The media pack, if you want to install it, should also be downloaded and will be called "FfH2media.exe".) Install FfH2 to "[path]\Beyond the Sword\Mods" (where [path] is replaced by the path to your installation of Civ 4), then install the Media Pack if you care to (also to "[path]\Beyond the Sword\Mods"), then install Patch O (again, to "[path]\Beyond the Sword\Mods").
Once these steps have been completed successfully you should be able to play FfH2. I explain the details more fully in my thread
How to Install FfH2. If you have any problems please consult that thread, and if your problem isn't solved there then let me know.