How to clone a struct storing a boxed trait object?

There are a few problems. The first is that there's nothing to require that an Animal also implements Clone. You could fix this by changing the trait definition:

trait Animal: Clone {
    /* ... */
}

This would cause Animal to no longer be object safe, meaning that Box<dyn Animal> will become invalid, so that's not great.

What you can do is insert an additional step. To whit (with additions from @ChrisMorgan's comment).

trait Animal: AnimalClone {
    fn speak(&self);
}

// Splitting AnimalClone into its own trait allows us to provide a blanket
// implementation for all compatible types, without having to implement the
// rest of Animal.  In this case, we implement it for all types that have
// 'static lifetime (*i.e.* they don't contain non-'static pointers), and
// implement both Animal and Clone.  Don't ask me how the compiler resolves
// implementing AnimalClone for Animal when Animal requires AnimalClone; I
// have *no* idea why this works.
trait AnimalClone {
    fn clone_box(&self) -> Box<dyn Animal>;
}

impl<T> AnimalClone for T
where
    T: 'static + Animal + Clone,
{
    fn clone_box(&self) -> Box<dyn Animal> {
        Box::new(self.clone())
    }
}

// We can now implement Clone manually by forwarding to clone_box.
impl Clone for Box<dyn Animal> {
    fn clone(&self) -> Box<dyn Animal> {
        self.clone_box()
    }
}

#[derive(Clone)]
struct Dog {
    name: String,
}

impl Dog {
    fn new(name: &str) -> Dog {
        Dog {
            name: name.to_string(),
        }
    }
}

impl Animal for Dog {
    fn speak(&self) {
        println!("{}: ruff, ruff!", self.name);
    }
}

#[derive(Clone)]
struct AnimalHouse {
    animal: Box<dyn Animal>,
}

fn main() {
    let house = AnimalHouse {
        animal: Box::new(Dog::new("Bobby")),
    };
    let house2 = house.clone();
    house2.animal.speak();
}

By introducing clone_box, we can get around the problems with attempting to clone a trait object.

It appears you want an associated type:

pub trait Algorithm<T> {
    type Output;

    fn calculate_something(&self) -> Result<Self::Output, Error>;
}

impl<T> Algorithm<T> for Sphere<T> {
    type Output = Sphere<T>;

    fn calculate_something(&self) -> Result<Self::Output, Error> {
        unimplemented!()
    }
}

impl<T> Algorithm<T> for Hyperbola<T> {
    type Output = Hyperbola<T>;

    fn calculate_something(&self) -> Result<Self::Output, Error> {
        unimplemented!()
    }
}

Associated types are described in detail in The Rust Programming Language. I highly recommend reading through the entire book to become acquainted with what types of features Rust has to offer.

An alternate solution is to define another generic type on the trait:

pub trait Algorithm<T, Out = Self> {
    fn calculate_something(&self) -> Result<Out, Error>;
}

impl<T> Algorithm<T> for Sphere<T> {
    fn calculate_something(&self) -> Result<Sphere<T>, Error> {
        unimplemented!()
    }
}

impl<T> Algorithm<T> for Hyperbola<T> {
    fn calculate_something(&self) -> Result<Hyperbola<T>, Error> {
        unimplemented!()
    }
}

You then need to decide When is it appropriate to use an associated type versus a generic type?

I currently know of no way a closure may be used as part of a return type other than using impl or Box, both of which you have mentioned and cannot be used in this situation.

An alternative would be to use a function pointer instead of a closure, like so:

fn return_command_instance() -> Command<u8, u8, fn(u8) -> Result<u8, Box<CommandError>>> {
    Command::define(|n: u8| Ok(n * 2))
}

Notice the lower case fn to signify a function pointer and not the trait Fn. This is explained in more details in the chapter on Advanced Functions & Closures.

This will only work if you do not capture any variables in the function, if you do it will be compiled into a closure.