Why are constructors indeed called "Constructors" ?

The constructor (named __new__) creates and returns a new instance of the class. So the C.__new__ class method is the constructor for the class C.

The C.__init__ instance method is called on a specific instance, after it is created, to initialise it before being passed back to the caller. So that method is the initialiser for new instances of C.

How are they different from methods in a class?

As stated in the official documentation __init__ is called after the instance is created. Other methods do not receive this treatment.

What is their purpose?

The purpose of the constructor C.__new__ is to define custom behaviour during construction of a new C instance.

The purpose of the initialiser C.__init__ is to define custom initialisation of each instance of C after it is created.

For example Python allows you to do:

class Test(object):
    pass

t = Test()

t.x = 10   # here you're building your object t
print t.x

But if you want every instance of Test to have an attribute x equal to 10, you can put that code inside __init__:

class Test(object):
    def __init__(self):
        self.x = 10

t = Test()
print t.x

Every instance method (a method called on a specific instance of a class) receives the instance as its first argument. That argument is conventionally named self.

Class methods, such as the constructor __new__, instead receive the class as their first argument.

Now, if you want custom values for the x attribute all you have to do is pass that value as argument to __init__:

class Test(object):
    def __init__(self, x):
        self.x = x

t = Test(10)
print t.x
z = Test(20)
print t.x

I hope this will help you clear some doubts, and since you've already received good answers to the other questions I will stop here :)