Installed shapely using pip, and had the same problem. So I went ahead and installed it like so:
sudo apt-get install libgeos-dev
And it worked. I’m running Ubuntu, so if you’re on Fedora, you should run:
sudo yum install geos-devel
On MACOS you can run:
brew install geos