How can you accelerate without moving? I know this question has been asked in other forms, generally regarding the balance of forces.  This time I want to focus on motion.  I've got a laser accelerometer on my desk.  It tells me that I'm accelerating at $9.8~\rm m/s^2$.  For the first experiment I'm travelling in space.  I pick a nearby star and discover that I move about $490$ meters in $10$ seconds from that star.  For the next experiment I'm on the surface of Earth.  I measure the same acceleration with my laser accelerometer.  I pick a spot (the center of the Earth) and discover I don't move at all in $10$ seconds.  How is acceleration without motion possible?
 A: The accelerometer doesn't measure 'movement' it measures acceleration. (I know that sounds tautological, but bear with me.) That is, it should read zero when in inertial (unaccelerated) motion, and when it reads non-zero a frame of reference at rest relative the instrument is non-inertial.
In other words the accelerometer is a tool for identifying inertial frames.
So here's the kicker: despite the treatment of physics you'll get in a Physics 101 classroom, standing still on on the floor of the lab is not inertial movement and a coordinate system that is at rest relative the floor is not an inertial frame (even neglecting the rotation of the planet). But one falling freely in that lab is an inertial frame.
Gravity, which we treat as a force in Physics 101 is more properly conceived of as a inertia pseudo-force like the centrifugal and Coriolis (pseudo-)forces. (And like those other pseudo forces it exhibits the feature of being precisely proportional to the mass of the affected object, so that all objects exhibit the same acceleration in the same circumstances.)
This is a core feature of general relativity.
For day-to-day purposes it remains easier to work in the non-inertial frame where the floor is at rest and simply add the inertial pseudo-force of magnitude $mg$ directed downward to your calculation.
A: In relativity (both flavours) we consider trajectories in four dimensional spacetime, and acceleration is a four-vector not a three-vector as in Newtonian mechanics. We call this four-acceleration while the Newtonian acceleration is normally referred to as coordinate acceleration.
Supoose we pick some coordinate system $(t,x,y,z)$ and measure the trajectory of some observer in these coordinates. The way we usually do this is to express the value of the coordinates as a function of the proper time of the observer, $\tau$. That is the position is given by the functions $\left(t(\tau), x(\tau), y(\tau), z(\tau)\right)$. The proper time $\tau$ is just the time recorded by a clock travelling with the observer, so we are describing the trajectory by how the position in our coordinates changes with the observer's time.
If we start by considering special relativity, i.e. flat spacetime, then the four-velocity and four-acceleration are calculated by differentiating once and twice respectively wrt time, just like in Newtonian mechanics. However we differentiate wrt the proper time $\tau$. So the four-velocity $U$ and four-acceleration $A$ are:
$$ \mathbf U = \left( \frac{dt}{d\tau}, \frac{dx}{d\tau}, \frac{dy}{d\tau}, \frac{dz}{d\tau} \right) $$
$$ \mathbf A = \left( \frac{d^2t}{d\tau^2}, \frac{d^2x}{d\tau^2}, \frac{d^2y}{d\tau^2}, \frac{d^2z}{d\tau^2} \right) $$
The four acceleration defined in this way is coordinate independent, and it behaves in a very similar way to Newtonian acceleration. For example we can (though we usually don't) write a relativistic equivalent of Newton's second law:
$$ \mathbf F = m \mathbf A $$
where $\mathbf F$ is the four-force.
To complete the comparison with Newtonian mechanics we can choose our $(t,x,y,z)$ to be the coordinates in which the accelerating observer is momntarily at rest, and in these coordinates the four-acceleration becomes the proper acceleration, which is just the acceleration felt by the observer. Let me emphasise this because we'll use it later:

the four-acceleration is equal to the acceleration felt by the observer in their rest frame.

Anyhow, this is all in flat spacetime, and in flat spacetime a non-zero four-acceleration means that in every inertial frame the position of the observer is changing with time. This ties up with the first part of your paragraph where you're talking about your position relative to a star changing with time. However in general relativity the expression for the four-acceleration has to include effects due to the curvature, and it becomes:
$$ A^\alpha = \frac{d^2x^\alpha}{d\tau^2} + \Gamma^\alpha_{\,\,\mu\nu}U^\mu U^\nu \tag{1} $$
I've written this using Einstein notation as it's rather long to write out otherwise. The index $\alpha$ is zero for $t$, one for $x$, two for $y$ and three for $z$. The new parameters $\Gamma^\alpha_{\,\,\mu\nu}$ in the equation are the Christoffel symbols that describe how the spacetime is curved.
The difference from flat spacetime is that now we can have a (locally) inertial frame, where the spatial coordinates are not changing with time, and we can still have a non-zero four-acceleration. That is even if $x$, $y$ and $z$ are constant, so $d^2x/d\tau^2$ etc are zero, the contribution from the Christoffel symbols means the four-acceleration $\mathbf A$ can still be non-zero.
And in general relativity it's still true that the four acceleration is the same as the acceleration felt by the observer in their rest frame, and this is the link to the second part of your question. Because of the curvature you can be (spatially) at rest on the surface of the Earth with respect to the distant star but still have a non-zero four-acceleration. But remember that above we said:

the four-acceleration is equal to the acceleration felt by the observer in their rest frame.

That means even though you are at rest in your coordinates your non-zero four-acceleration means you still feel an acceleration. That acceleration is of course just what we call gravity.
Response to comment: Moving in a straight line
The obvious way to define motion in a straight line is to say that the acceleration is zero. In Newtonian mechanics this is just Newton's first law, where the acceleration is the coordinate acceleration $\mathbf a$. Likewise in relativity (both flavours) a straight line means the four-acceleration $\mathbf A$, defined by equation (1) above, is zero. Looking at equation (1), the only way for $\mathbf A$ is if the $dx^\alpha/d\tau^2$ term exactly balances out the Christoffel symbol i.e.
$$ \frac{d^2x^\alpha}{d\tau^2} = -\Gamma^\alpha_{\,\,\mu\nu}U^\mu U^\nu \tag{2} $$
This equation is called the geodesic equation, and it describes the trajectory of a freely falling particle in a curved spacetime. That is, it is the equation for a straight line in curved spacetime or more formally a geodesic.
Actually solving the geodesic equation is usually hard (like most things in GR) but for an overview of how this equation describes things falling in Earth's gravity see How does "curved space" explain gravitational attraction?.
Footnote: The elevator, the rocket, and gravity: the equivalence principle
The above discussion provides a nice way to understand the elevator/rocket description of the equivalence principle. See this article for a full discussion, but in brief suppose you are inside a lift with the doors closed so you can't see out. You can feel a force pulling you down with an acceleration of $1$g, but you can't tell if the lift is stationary on the Earth and you're feeling gravity, or if you're in outer space and the lift has been attached to a rocket accelerating at $1$g.
To see why this is we take equation (1) and rewrite it as:
$$ \mathbf A = \mathbf A_\text{SR} + \mathbf A_\text{GR} \tag{3} $$
where $\mathbf A_\text{SR}$ is the term we get from special relativity, $d^2x^\alpha/d\tau^2$, and $\mathbf A_\text{GR}$ is the term we get from general relativity, $\Gamma^\alpha_{\,\,\mu\nu}U^\mu U^\nu$.
But all you can measure is $\mathbf A$. Remember that $\mathbf A$ is equal to the acceleration in your rest frame, so if you have a set of scales in the lift you can measure your weight, divide by your mass, and you get your proper acceleration $\mathbf A$.
The point is that although you can experimentally measure the left side of equation (3) the equivalence principle tells us that you can't tell what is on the right hand side. If the elevator is blasting through space on a rocket $\mathbf A_\text{GR}$ is zero and all your acceleration comes from $\mathbf A_\text{SR}$. Alternatively if the elevator is stationary on Earth $\mathbf A_\text{SR}$ is zero and your acceleration comes from the $\mathbf A_\text{GR}$ term. The equivalence principle tells us that there is no way for you to tell the difference.
