Constructors - lots of paramters or none and use of set methods

In your opinion what is the best way to construct an object given the two examples below:

Option 1: Lots of parameters

private string firstname;
private string surname;
private Address homeAddress;
private PhoneNumber homeNumber;

public Person(string firstname, string surname, Address homeAddress, 
              PhoneNumber homeNumber)
{
    _firstname = firstname;
    _surname = surname;
    _homeAddress = homeAddress;
    _homeNumber = homeNumber;
}

public string getFirstname()
{
    return firstname;
}

public string getSurname()
{
    return surname;
}

public Address getAddress()
{
    return address;
}

public PhoneNumber getHomeNumber()
{
    return _homeNumber;
}

Option 2: no parameters and use of set methods

private string firstname;
private string surname;
private Address homeAddress;
private PhoneNumber homeNumber;

public Person()
{
}

public string getFirstname()
{
    return firstname;
}
public void setFirstname(String value)
{
    firstname = value;
}

public string getSurname()
{
    return surname;
}
public void setSurname(String value)
{
    surname = value;
}

public Address getAddress()
{
    return address;
}
public void setAddress(Address value)
{
    address = value;
}

public PhoneNumber getHomeNumber()
{
    return _homeNumber;
}
public void setHomeNumber(PhoneNumber value)
{
    _homeNumber = value;
}

Which method do you prefer? In my mind, option 1 is better because you know that the state of your object cannot be changed. I believe this is called immutability and is something that should be desired? On the other hand, it can quickly get out of hand and ugly if you have more than a handful of parameters.

I am aware that some languages such as C# have nice features that would probably make option 1 more appealing such as named and optional parameters however this question was prompted while dealing with Java code.

Update: Thank you for all of your suggestions. I will comment on each answer individually but a few

It depends on whether the data elements are required for the object to be well defined or if they are completely optional.

My personal preference is for the constructor to have parameters for all the required data elements and use set methods for everything else. I also declare the default (parameterless) constructor to be private. That way the compiler guarantees that no one will create an incompletely defined object.

If firstname and lastname are required but address and phone number are optional, I would do the following:

private string _firstname;
private string _surname;
private Address _homeAddress;
private PhoneNumber _homeNumber;

private Person()
{
    // Ensure unitialized Person cannot be created
}

public Person(string firstname, string surname)
{
    _firstname = firstname;
    _surname = surname;
}

// getters and setters omitted for brevity

The disadvantage of using the Builder pattern as recommended in other answers is that the completeness check is deferred to runtime. If you have a code path that is very rarely executed and you change Person so that more data is required, then you could deliver code that will fail in the field. With my approach, you will know about the problem the next time you try to compile your code.

StackExchange Code Review Q#3462, answer score: 10