Validating basic data objects
Let's look at all of your questions, one by one:

This class doesn't really do anything, and is really a pretty struct

Yes and no. This class has a clear task within the application: it is passed around, carrying data. It represents a number of values that belong together. It's a model. Having data containers isn't just OK, it's good practice. You can use type-hinting, and doc-blocks to make your code easier to use.
You call it a glorified struct, well: in C, a FILE * is just a struct, too, but you rarely use it as such: There's an entire API that handles the nitty-gritty for you, in the same way that you can use this model to validate the data you are setting.

Code that requires this data, either to store it in a DB, or present it to the client side in a view, can then be written with a clear contract:

public function showRecipient(Recipient $recipient)
{
    //if an instance is passed, its email address is expected to be set and valid
}


But how do you best make sure when, and where to validate the email address:

The validation isn't specific to this place, I may want to check emails in other places

Don't. If you are processing data that belongs to, or is part of the dataset that makes up a Recipient, the thing to do is to wrap this data in the appropriate container: a Recipient instance.
If you validate the email elsewhere in your code, you are repeating yourself. Simply pour it into an object, that makes sure the data is valid, and pass that object around. Whatever values you extract from it (through getters), is guaranteed to be validated.

Should the validation happen in the constructor? Should it be a separate class? What would that look like?

The validation should Not be done in the constructor. I can construct an instance, and re-assign/reset the properties to a particular value, bypassing the constructor's  validation.
A separate class, then? No. Really... why would you centralize all data validation/sanitation? Such a class would be either an all-static monster, or you'd initialize all validation code, every time you want to validate a single value.

I'd make my properties protected, and use setters. These setter methods are tailored to the type of property they are setting, and can perform the necessary sanitation and validation. Simple.

Should there be an interface for every class? Would that live at the top of this file?

Depends. Is it worth while? Are there similarities between other models (database mapping: getId() and setId methods)? Is there a certain type of functionality you want to add (for example implementing one of the Traversable interfaces).
Hard to say from what code you shared, but if this is the only data-class then: no. An interface is probably not required.

Should I throw exceptions when it's not valid? Should they be an object as well? How?

Yes: a class has just one job. This class' job is to contain valid data. Raw data is passed to its setters, which validate/sanitize this data. If the data is malformed/invalid, the Recipient class is not responsible for it: the code that supplied the data is. The Recipient should throw an exception (it encountered exceptionally formed data), and the calling code should handle the problem.
Should these exceptions be objects: Of course, they are. There's no way around them. If you mean: should I throw or set a property, the answer is: throw. Your class encountered a problem. Setting a property or returning false assumes the calling code is checking return values or flags. This is not a given (return values are often ignored, and error flags seldom checked).
Throwing an exception forces the calling code to respond

To answer the how question, here's how I'd write your class:

class Recipient
{
    protected $email = null;
    protected $name = null;
    public function __construct(array $data = array())
    {
        foreach ($data as $key =&gt; $val)
        {
            //transform key to method
            $method = 'set'.ucfirst(strtolower($key));
            if (method_exists($this, $method))
                $this-&gt;{$method}($val);
        }
    }
    public function setEmail($email)
    {
        if (!filter_var($email, FILTER_VALIDATE_EMAIL))
        {//not a valid email address, throw exception
            throw new InvalidArgumentException(
                sprintf(
                    '%s expects valid email address, %s is not',
                    __METHOD__,
                    $email
                )
            );
        }
        $this-&gt;email = $email;
        return $this;
    }
    public function setName($name)
    {
        //add checks/sanitation you need: check length, check format, check for numeric chars... 
        $this-&gt;name = trim($name);
        return $this;
    }
    public function getEmail()
    {
        return $this-&gt;email;
    }
    public function getName()
    {
        return $this-&gt;name;
    }
}


That should do it. Usage examples:

$data = array('email' =&gt; 'foo@bar.com', 'name' =&gt; 'foo');
$recipient = new Recipient($data);
echo 'From instance - email: ', $recipient-&gt;getEmail();
$recipient-&gt;setName('    Foo');
echo 'After setter: ', $recipient-&gt;getName();//leading spaces are removed


Now, why did I default the constructor argument to an empty array? Simply because it allows you to do this:

$blank = new Recipient();
$obj-&gt;EmailGetter($queryObject, $blank);//gets email, sets it on instance
$blank-&gt;setName('Unknonwn');


I can create an object, then fetch the data as I go along, and set the properties accordingly.
As far as the exception business is concerned:

$error = new Recipient(
    array(
        'email' =&gt; 'invalid'
    )
);//error
//or
$test = new Recipient();
$value = 'invalidaddress';
try
{
    $test-&gt;setEmail($value);
    echo 'If $value is valid, this will echo its value again here: ', $test-&gt;getEmail();
}
catch (InvalidArgumentException $e)
{//echos "invalidaddress was refused:  Recipient::setEmail expects valid email address invalidaddress is not"
    echo $value, ' was refused: ', $e-&gt;getMessage();
}


I've reviewed a couple of validation + data-model related questions, so I thought I'd add some of my (lengthy) reviews here, too. For completeness' sake:


details on Traversable interface
Bulk setting + inheritance
Some more bulk setting
Vaguely related