When I was young, the thought of a communicator with global reach that I could pull out of my pocket, tap and then say the name of who I'd like to be connected to seemed surely to be science fiction. I assumed it to be in the second category as well, because I couldn't conceive of a radio transmitter powerful enough to reach around the world that could fit in my pocket. I completely missed the fact that there might be a global, semi-self-organizing packet switched network involved. Sci-fi became real in my lifetime and it was awesome.
Being a strict naturalist (no belief in supernatural "spirits" or "souls" or what have you) I can't see how a hunk of meat that fits in an 11cm box, only takes 20 watts to power, and is replicated in nature by the billions should be fundamentally be un-simulate-able (and then improvable).
Its sci-fi because the technical challenge seems insurmountable by today's standards, but I'd place it firmly in the first category, not the second.