Several differences, in fact.
For one thing, the first argument in __new__ and __init__ are not the same, which is not made clear by everyone insisting on just using cls in both cases (despite the fact that the variable name doesn't hold any particular meaning).  Someone pointed this out and it's core to understanding the difference:
- __new__gets the metaclass -- MyTypein my example (remember the application-level class is not created yet).  This is where you can alter- bases(which can cause MRO resolution errors if you're not careful).  I'll call that variable- mcls, to differentiate it from the usual- clsreferring to application level class.
 
- __init__gets the newly-created application-level class,- Barand- Fooand, by that time, this class's namespace has been populated, see- cls_attribin example below.  I'll stick to- clsas per usual naming convention.
 
Sample code:
class Mixin:
    pass
class MyType(type):
    def __new__(mcls, name, bases, attrs, **kwargs):
        print("  MyType.__new__.mcls:%s" % (mcls))
        if not Mixin in bases:
            #could cause MRO resolution issues, but if you want to alter the bases
            #do it here
            bases += (Mixin,)
        #The call to super.__new__ can also modify behavior:
        #                                    classes Foo and Bar are instances of MyType
        return super(MyType, mcls).__new__(mcls, name, bases, attrs)
        #now we're back to the standard `type` 
        #doing this will neuter most of the metaclass behavior, __init__ wont
        #be called.                         
        #return super(MyType, mcls).__new__(type, name, bases, attrs)
    def __init__(cls, name, bases, attrs):
        print("  MyType.__init__.cls:%s." % (cls))
        
        #I can see attributes on Foo and Bar's namespaces
        print("    %s.cls_attrib:%s" % (cls.__name__, getattr(cls, "cls_attrib", None)))
        return super().__init__(name, bases, attrs)
print("\n Foo class creation:")
class Foo(metaclass=MyType):
    pass
print("\n bar class creation:")
class Bar(Foo):
    #MyType.__init__ will see this on Bar's namespace
    cls_attrib = "some class attribute"
output:
 Foo class creation:
  MyType.__new__.mcls:<class '__main__.test.<locals>.MyType'>
  MyType.__init__.cls:<class '__main__.test.<locals>.Foo'>.
    Foo.cls_attrib:None
 Bar class creation:
  MyType.__new__.mcls:<class '__main__.test.<locals>.MyType'>
  MyType.__init__.cls:<class '__main__.test.<locals>.Bar'>.
    Bar.cls_attrib:some class attribute