"There is a small convenience store by the hospital."
隣 is used when two identical or very similar things are directly next to each other (to the side).
そば just means that one thing is in the vicinity of another thing. They need not be similar things and they need not be to the side. Anywhere within a short radius qualifies.
By can imply near rather than next to, so そば is appropriate. 隣 is not appropriate because we can't be certain that the store is next to the hospital.
Most of the time, in japanese sentences, the most important part is near the verb at the end of the sentence, this also include new information, most of the time marked by が, that's why you usually see が near the verb, not all the time, but yeah.
So in english when you say "There is a convenience store by the hospital" the most important part is the fact that there is a small convenience store, in the english structure, the rest is additional. If you want to apply emphasis on the location for the english structure you say "Right by the hospital, there is a convenience store".
In japanese is the other way, since new/important information needs to be near the verb then that means it needs to go at the end. In this case, the existence of the convenience store is the most important (that's the new information), you can presume this by taking the english sentence as a reference of what you want to say.
So from that we have「コンビニがある」now, we add the location「病院のそばに・コンビニがある」。。And we add the modifier (the adjective), and the masu form「病院のそばに小さなコンビニがあります」
If you find you are still having trouble with structure in japanese I recommend reading this guide:
it also explains how japanese sentences are formed from the bigger picture to the small, which is very related to why you usually see に、で particles right after は markers, and why do you see を near verbs as well.
Because using が here makes it look contrastive. In other words, it seems like the relevant new information is that the convenience store is what is near the hospital, rather than focusing on the location of the convenience store.
About the convenience store: it is near the hospital.
About what is near the hospital: it is the convenience store.