Use only OrientDB without any RDBMS

Way two is the correct way.

Your base class gets a table, and then child classes get their own tables with just the additional fields they introduce, plus foreign key references to the base table.

As Joel suggested in his comments on this answer, you can guarantee that a user will have either a direct login or an OpenID login, but not both (and also possibly neither) by adding a type column to each sub-type table that keys back to the root table. The type column in each sub-type table is restricted to have a single value representing the type of that table. Because this column is foreign keyed to the root table, only one sub-type row can link to the same root row at a time.

For example, the MySQL DDL would look something like:

CREATE TABLE Users
(
      uid               INTEGER AUTO_INCREMENT NOT NULL
    , type              ENUM("DirectLogin", "OpenID") NOT NULL
    // ...

    , PRIMARY_KEY(uid)
);

CREATE TABLE DirectLogins
(
      uid               INTEGER NOT_NULL
    , type              ENUM("DirectLogin") NOT NULL
    // ...

    , PRIMARY_KEY(uid)
    , FORIGEN_KEY (uid, type) REFERENCES Users (uid, type)
);

CREATE TABLE OpenIDLogins
(
      uid               INTEGER NOT_NULL
    , type              ENUM("OpenID") NOT NULL
    // ...

    PRIMARY_KEY(uid),
    FORIGEN_KEY (uid, type) REFERENCES Users (uid, type)
);

(On other platforms you would use a CHECK constraint instead of ENUM.) MySQL supports composite foreign keys so this should work for you.

Way one is valid, though you are wasting space in those NULL-able columns because their use depends on the type of user. The advantage is that if you choose to expand what kinds of user types to store and those types don't require additional columns, you can just expand the domain of your ENUM and use the same table.

Way three forces any queries that reference users to check against both tables. This also prevents you from referencing a single users table via foreign key.

I think the Notes table is missing a userID FK column (and put an index on it)
You need to identify the owner of the Note

The UserNotes table does not need an ID
just:

NoteID || UserId

That is a sufficient composite PK
And I would do it in that order for quick counting NoteID
select count(*) from UserNotes where NoteID = X would be very very fast

So what 1000 x 1000 rows. You have 1000 x 1000 unique relationships. It is just two Int.

One trick is have a UserID Public ID 0 for all

Just a preference but I don't use plural in a table name
Tables are used to store many rows