Stall speed is the speed below which the aircraft cannot continue with straight level flight. It shows up in the following equation:
nz*Weight=1/2 * rho * Vs-squared * CL-max * wing-area
So for any given aircraft the following will affect stall speed (Vs):
aircraft weight - the heavier you are, the faster the stall speed. Your 45kts must be for your typical weight.
nz, normal accel - since an aircraft at 2'g' needs to support 2 times the weight of a 1'g' case, you need to fly faster to fly at 2'g'.
rho - air density. If you are calculating Vs in true airspeed, then the higher you go, the faster the stall speed has to be, to compensate for reduced air density.
If you are using EAS it makes no difference, because you would always use sea level density in this equation.
If using CAS (or IAS) then you have to consider the "scale altitude correction" too. This will cause a variation in stall speed with altitude, even though the EAS will be the same.
wing are - the bigger the wing, the more it can lift, the lower the stall speed
CL-max - areodynamic maximum lift coefficient.
This can be influenced by a whole host of things - wing planform (straight wings are usually more efficient at generating lift), aerofoil section (including presence of flaps or slats), how usable the lift is - it's no use having a high theoretical CL-max if the controls cannot get you there (too small a tail, say) or if the stall is so abrupt that some kind of stall warning device has to be added ahead of the true stall.
There are some precise definitions of what the authorities consider to be a stall, which differ subtly in considering what is acceptable control behaviour.
Regarding your question about the fin in disturbed flow:
This can show up through reduced directional stability at higher angles of attack, where a wake shed from the upper surface of the fuselage may partially 'blank' the fin, reducing both directional stability and directional control (rudder power)
It may also occur as increased vibration and buffetting through the fin. I believe the X-29 and F-18 have both had significant vertical tail buffeting at higher angles of attack, and those little fences on later F-18s on top of the inboard wing are intended to disrupt the vortex which was causing the problem. I don't know of any civil aircraft where the effect was quite so pronounced; generally transport category aircraft don't get to such high angles of attack, for one thing.
Hope that helps a bit.