My opinion is always cache or queue if backend processing takes more than a second. There are some exceptions like "search" or "scrape", but other than that you should aim in 0.5 response time.
In your case 10 seconds to perform this request is a killer.

Let's imagine that you will encounter 250+ users performing image manipulation at the same time. With default LAMP stack your server load will hit the roof!!!

To achieve youtube like feedback you will need some clever front end magic such as WebSocket or less efficient setInterval function.

How to setup Laravel queue server : http://fideloper.com/ubuntu-beanstalkd-and-laravel4

Great Laravel/WebSocket implementation : https://github.com/BrainBoxLabs/brain-socket

These are 2 excellent links. I think I know where and what to evaluate.

I just have another question that worries me a bit at the moment. Your example of 250+ user using the service at the same time would be a great thing, meaning the service is a success. So far I have put that worry away with the assumption that in that case I would just upgrade/resize my droplet at digitalocean. Is this assumption correct. I guess in theory there must be a solution even with thousands of manipulaions at the same time, multiple servers sharing the load?

Also checkout Gearman PHP a good queue server