You should never need to put any .py or .pyc dependencies in a subfolder or in the same folder as your executable. So things like os.pyc or shutil.pyc should ALWAYS be embedded in your executable. This is done right before you build your executable in Cosntruct.
I don't think adding a __Init__.py helps with .pyd files (Python modules/dynamic link libraries). A __init__.py is typically used to specify import and other info for other .py or .pyc files in the same directory.
I won't have anytime to try this out this week, but if you haven't gotten it working by next weekend I might give it a shot to see what can be done with the .pyd files.