I'm honestly not sure Star Trek would have worked without Spock, at least not on the big screen. He's part of the triumvirate with Kirk and McCoy, and that is the heart of TOS.
I imagine that Paramount's greed would have led to another film after TWOK's success, but I can't imagine that version of Star Trek III doing well after the curiosity of opening weekend died down. Fans would have likely refused to watch the movie and general audiences would have to be really impressed with whatever followed something like the death of Spock. Spock's death, of course, had the effect of bringing in non-fans and would have been almost impossible to follow. Hell, that's why David Marcus and the Enterprise die as something big needed to happen before Spock's full return.
As for a Spock-less Trek III, I don't know where you can go that beats TWoK...maybe a direct threat to Earth? Do you just do The Voyage Home? That story doesn't work without Spock or, at least, isn't nearly as strong and classic.