Personal preference:
1.
Elijah and
Nathaniel [wow, my two top favorite boy names :)]
2.
Elijah and
Josiah (
Josiah is quite popular, at least here, but still substantial)
ties with
2.
Elijah and
Luke (
Luke is just more attractive sounding to me, and if that's what you're going to call him anyway, its a legit name on its own)
Other thoughts:
The only one I don't care for is
Lucas, though I love
Luke. I don't really care for Joe/Joey, and while
Nate and
Nathan are both great, I love
Nat for
Nathaniel (and I really like the spelling
Nathanael). I personally don't mind
Jackson, but although you said popularity doesn't bother you, I think
Jackson might be seen more as trendy than popular.