Unless your robot is experiencing sustained accelerations on the order of 1g, ignoring linear accelerations to compute the tilt angle should work well. Besides, typically the weight on the accelerometer measurement is much lower than that on the gyroscope measurement in a standard complementary filter so any linear accelerations should only add a small bias. How is your robot moving at startup? What sort of accelerations are you seeing?
If on startup, the robot is at an arbitrary orientation AND experiencing excessive linear accelerations (not velocities), then it may be tricky as the initial orientation computed may be quite wrong. In that case, if there is any way to know the linear motion in advance, e.g. if the motion is a result of control inputs, then that known acceleration can be subtracted before the accelerometer readings are used in the filter.
A particularly tricky case may be when the robot starts in free fall. If it doesn't hit terminal velocity to experience a drag force, and without any other forces acting on it, I don't see a way to measure the tilt relative to the ground with an accelerometer and gyroscope. The accelerometer will measure all zeros and give no tilt information. However, the drag force in most situations may be enough to give some bearing, but you are not guaranteed that the force is parallel to the force of gravity.
If one wishes to estimate the tilt of a robot in a parabolic free fall with air resistance. Then I can imagine some algorithm that attempts to estimate the tilt using the direction of the drag force and some estimated progress along a parabolic arc. It sounds complicated though.
I'm not familiar with the Madgwick filter specifically, but to me it sounds like some variant of a complementary filter.