Mitch Albom, The Five People You Meet in Heaven, p. 11 paragraph 3:

But back at the Stardust Band Shell with Marguerite....

Mark Twain, The Adventures of Huckleberry Finn, last sentence of Chapter VI:

And how slow and still the time did drag along.

Henry Wadsworth Longfellow, The Song of Hiawatha, Introduction

"And the pleasant watercourses, you could trace them through the valley..."

Shakespeare, Hamlet, Prince of Denmark, Act 1, Scence 1, Horatious starts a speech:

And then it started like a guilty thing.

Also, Paul, in the letter to the Corinthians, on a number of occasions starts a sentence with "and" or "but".

[Yes, I know that the Twain citation is contained within dialog, and that the Longfellow citation is poetry, and the Shakespeare is from a play.]

Perhaps he's heard of the King James Bible? It may be hard to read now but it's been called one of the greatest works of the English language. I recommend starting on the first page:

In the beginning God created the heaven and the earth. And the earth was without form, and void; and darkness was upon the face of the deep. And the Spirit of God moved upon the face of the waters.

On a hunch I opened The Sound And The Fury by William Faulkner, once, at a random page and saw:

It was a while before the last stroke ceased vibrating. It stayed in the air, more felt than heard, for a long time. Like all the bells that ever rang still ringing in the long dying light-rays and Jesus and Saint Francis talking about his sister. Because if it were just to hell; if that were all of it. Finished. If things just finished themselves. Nobody else there but her and me. If we could just have done something so dreadful that they would have fled hell except us. I have committed incest I said Father it was I it was not Dalton Ames    And when he put Dalton Ames. Dalton Ames. Dalton Ames.

The choice of book wasn't random but I swear to you, I did not try multiple books or multiple pages. First time ;-)

Note that the initial "because" isn't always "grammatically incorrect", but in this case Faulkner uses it to introduce a dangling subordinate clause. There are some other sentence fragments with "if". There isn't actually a period in my edition before the "And", but to the extent that stream-of-consciousness writing can be said to have sentences at all, I think this starts one.

So I'm not sure that "great writers" are necessarily good authorities on style, since they fairly predictably break any "bureaucratic" rule you can think of for effect. In this case, the initial conjunctions are no barrier at all to clear communication (although perhaps the content itself is obscure). Even rules that you'd think are necessary for clear communication can go out of the window, though, to a particular end. The act of breaking a rule is in itself significant, and doesn't necessarily negate the rule's common applicability.

So, while the many examples given in other answers are excellent demonstrations that this particular "rule" is silly, beware arguing from the greatness of the author!

Examples from Tolkien’s Legendarium

For my own demonstrative examples, I’ve chosen just one “great writer”, so that some measure of frequency of this phenomenon within a single writer’s works can be taken.

Across The Silmarillion, The Hobbit, and The Lord of the Rings, J.R.R. Tolkien began sentences with these seven (potential) conjunctions the indicated number of times each, sorted in descending order of frequency:

False Positives

Because those just count sentence-starts, not running the text through a syntactic analyser to determine actual parts of speech, the numbers of at least some are inflated due to false positives.

Although but and so also have some false positives as well, this is perhaps more true of for than of the others. This is because for is much more often used as a preposition than as a conjunction. About conjunctive uses of for, the OED has this to say:

The use of for as a conj. has not been found earlier than the 12th c. The older lang. supplied the place of the conj. by locutions in which for prep. governed a neuter demonstrative pronoun followed by a relative particle: for ðon ðe, for ðý ðe, etc. (see for-thon, for-thy). The conjunctional use of for = for ðon ðe may be explained either as an extension of the functions of the prep. to govern a noun-sentence, or as an ellipsis.

In OE. for and fore seem to have been used indiscriminately as preps.; in ME. they were gradually differentiated.

B. conj.

---

• † 1. Introducing the cause of a fact, the statement of which precedes or follows: Because. Cf. ^{A. 21 b.} Obs. exc. arch.
• 2 a. Introducing the ground or reason for something previously said: Seeing that, since. Cf. Gr. γάρ, L. nam or enim, Fr. car, Ger. denn.
• 2 b. Introducing a detailed proof.

For while using for as a conjunction may sound literary or at times even archaic, it surely does occur in the register that Tolkien was writing in.

Corporal Citations

Below I provide three random samples from each set for each of the seven coordinating conjunctions which I tested for, generally one apiece from each of the three words named above:

But

• But above this gate, and behind it even to the mountains, he piled the thunderous towers of Thangorodrim, that were made of the ash and slag of his subterranean furnaces, and the vast refuse of his tunnellings.

• But after ages alone in the dark Gollum’s heart was black, and treachery was in it.
• But against this Gandalf had spoken urgently, because of the evil that dwelt in the valley, where the minds of living men would turn to madness and horror, and because also of the news that Faramir had brought.

And

• And all the coasts and seaward regions of the western world suffered great change and ruin in that time; for the seas invaded the lands, and shores foundered, and ancient isles were drowned, and new isles were uplifted; and hills crumbled and rivers were turned into strange courses.

• And after all he never had any real hope in the affair from the beginning; but being a cheerful hobbit he had not needed hope, as long as despair could be postponed.
• And all those rings that he governed he perverted, the more easily since he had a part in their making, and they were accursed, and they betrayed in the end all those that used them.

For

• For as has been told and as is known to all, being written in lore and sung in many songs, Melkor slew the Trees of the Valar with the aid of Ungoliant, and escaped, and came back to Middle-earth.

• For he saw spiders swarming up all the neighboring trees, and crawling along the boughs above the heads of the dwarves.
• For there shall walk a power in the forests whose wrath they will arouse at their peril.

So

• So after a brief rest they set out again and were soon lost in a shadowy silent world, cut off from all view of the lands about, either the hills that they had left or the mountains that they sought.

• So following the hobbit, down into the lowest cellars they crept.
• So between them our enemies have contrived only to bring Merry and Pippin with marvellous speed, and in the nick of time, to Fangorn, where otherwise they would never have come at all!

Yet

• Yet after the fall of Sauron their power was ever at work, and where they abode there mirth also dwelt and all things were unstained by the griefs of time.

• Yet as Gimli after learned it was still two hours ere sunset of the day on which they had set out from Dunharrow; though for all that he could then tell it might have been twilight in some later year, or in some other world.
• Yet for a while I stand in the place of the Steward of Gondor, and it is mine to think first of its people.

Or

• Or because I do not go, and you desire still to be near me.

• Or why should I sit here in my tower and think, and watch, and wait, spending even my sons?
• Or would be, if Lugbúrz would let him alone.

Nor

• Nor could the stronghold of Morgoth be ever wholly encircled: for the Iron Mountains, from whose great curving wall the towers of Thangorodrim were thrust forward, defended it upon either side, and were impassable to the Noldor, because of their snow and ice.

• Nor did they hear or feel him trotting along well behind their torch-light as they led off their prisoners into the forest.
• Nor in all my realm shall it be openly spoken, while my power endures.

Special Effects

There is nothing especially unusual, let alone remarkable, about beginning a sentence with a coordinating conjunction.

At times, though, this is done for purposeful effect. The most intense such effect in all of Tolkien’s writings occurs in the following passage from the end of The Lord of the Rings when Faramir and Éowyn await news of the Captains of the West, who had gone off to the Black Gate while those two lay in the Houses of the Healing.

After the Ring is destroyed, a great eagle appears, truly a messenger of the “gods” (the Valar) sent to bring good tidings of great joy to a beleaguered people. A new day is dawning in the city of the Tower of the Guard (Minas Tirith), for the eagle gives the city its old name back, the Tower of the Sun (Minas Anor). The entire scene explodes with light.

Here the repetitive lines starting over and over again with either and or for are deliberately meant to evoke the Hebrew psalms as translated into the King James Version of the Bible.

To anyone familiar with the Psalms — as would all readers have been when Tolkien wrote it — the effect is a sublimely powerful one. The Sing and rejoice is clearly from the Psalms, as is the repetition of the conjunctions. And lest there be any doubt remaining that this were done with full intent aforethought, he reverts to the Early Modern English of the KJV: note all the instances of ye and hath.

The following excerpt occurs in the chapter “The Stewart and the King” from Book VI of The Lord of the Rings by J.R.R. Tolkien (bold emphasis mine, to show the parts meant to evoke the Psalms):

      And so they stood on the walls of the City of Gondor, and a great wind rose and blew, and their hair, raven and golden, streamed out mingling in the air. And the Shadow departed, and the Sun was unveiled, and light leaped forth; and the waters of Anduin shone like silver, and in all the houses of the City men sang for the joy that welled up in their hearts from what source they could not tell.

      And before the Sun had fallen far from the noon out of the East there came a great Eagle flying, and he bore tidings beyond hope from the Lords of the West, crying:

          Sing now, ye people of the Tower of Anor,
          for the Realm of Sauron is ended for ever,
              and the Dark Tower is thrown down.

          Sing and rejoice, ye people of the Tower of Guard,
          for your watch hath not been in vain,
          and the Black Gate is broken,
          and your King hath passed through,
              and he is victorious.

          Sing and be glad, all ye children of the West,
          for your King shall come again,
          and he shall dwell among you
              all the days of your life.

          And the Tree that was withered shall be renewed,
          and he shall plant it in the high places,
              and the City shall be blessed.

              Sing all ye people!

   And the people sang in all the ways of the City.

Now go back and try rewriting that passage without any instances of and and for at the beginning of the sentences and independent clauses within. It is an interesting experiment: you will see this scintillating passage deflate like a beach ball all of whose air has escaped it.

We should all be grateful that Tolkien was a Professor of English, not someone cowed into insipid writing by obsequious obedience to fake “rules” which are themselves nothing but figments of prescriptivists’ cruel unimaginations, for we should not otherwise have such stirring words of joy to inspire us.

I suppose I'm just piling on, since so many examples have already been provided. But when we are dispelling a persistent myth, there's no need to pull back any punches!

Here are 10 counterexamples breaking this so-called Tenth Commandment of Grammar; these authors would likely be considered "great writers" by most.

I. The Thirty Mile River was wide open. Its wild water defied the frost, and it was in the eddies only and in the quiet places that the ice held at all. Six days of exhausting toil were required to cover those thirty terrible miles. And terrible they were, for every foot of them was accomplished at the risk of life to dog and man. A dozen times, Perrault, nosing the way broke through the ice bridges, being saved by the long pole he carried, which he so held that it fell each time across the hole made by his body. But a cold snap was on, the thermometer registering fifty below zero, and each time he broke through he was compelled for very life to build a fire and dry his garments.
      (Jack London, The Call of the Wild)

II. At first Bartleby did an extraordinary quantity of writing. As if long famishing for something to copy, he seemed to gorge himself on my documents. There was no pause for digestion. He ran a day and night line, copying by sun-light and by candle-light. I should have been quite delighted with his application, had he been cheerfully industrious. But he wrote on silently, palely, mechanically.
      (H. Melville, Bartleby the Scrivener)

III. There was a piece of ornamental water immediately below the parapet, on the other side, into which Mr. James Harthouse had a very strong inclination to pitch Mr. Thomas Gradgrind junior, as the injured men of Coketown threatened to pitch their property into the Atlantic. But he preserved his easy attitude; and nothing more solid went over the stone balustrades than the accumulated rosebuds now floating about, a little surface-island.
      (Dickens, Hard Times)

IV. Many days passed before we could speak to the Golden One again. But then came the day when the sky turned white, as if the sun had burst and spread its flame in the air, and the fields lay still without breath, and the dust of the road was white in the glow. So the women of the field were weary, and they tarried over their work, and they were far from the road when we came. But the Golden One stood alone at the hedge, waiting. We stopped and we saw that their eyes, so hard and scornful to the world, were looking at us as if they would obey any word we might speak.
      (A. Rand, Anthem)

V. At the next corner she got out, of course; and as she had no more money, she had to walk the rest of the way to the yards in the pouring rain. And so all day long she sat shivering, and came home at night with her teeth chattering and pains in her head and back.
      (Upton Sinclair, The Jungle)

VI. Men and women came to see her, met her down town, where she went to do her marketing, brought her home in their cars--and came in for a moment to talk and to rest, in the glamour that still played in her smile. But men who did not know her no longer followed her with admiring glances in the street; a diaphanous veil had come down over her beauty, destroying its vividness, yet bringing neither wrinkles nor fat.
      (Fitzgerald, The Lees Of Happiness)

VII. About midnight, while we still sat up, the storm came rattling over the Heights in full fury. There was a violent wind, as well as thunder, and either one or the other split a tree off at the corner of the building: a huge bough fell across the roof, and knocked down a portion of the east chimney-stack, sending a clatter of stones and soot into the kitchen-fire. We thought a bolt had fallen in the middle of us; and Joseph swung on to his knees, beseeching the Lord to remember the patriarchs Noah and Lot, and, as in former times, spare the righteous, though he smote the ungodly. I felt some sentiment that it must be a judgment on us also. The Jonah, in my mind, was Mr. Earnshaw; and I shook the handle of his den that I might ascertain if he were yet living. He replied audibly enough, in a fashion which made my companion vociferate, more clamorously than before, that a wide distinction might be drawn between saints like himself and sinners like his master. But the uproar passed away in twenty minutes, leaving us all unharmed; excepting Cathy, who got thoroughly drenched for her obstinacy in refusing to take shelter, and standing bonnetless and shawl-less to catch as much water as she could with her hair and clothes.
      (E. Bronte, Wuthering Heights)

VIII. It was nearly half-past twelve. He had just come back from church, hoarse and weary with preaching. He preached with fury, with passion, an iron man beating with a flail upon the souls of his congregation. But the souls of the faithful at Crome were made of india-rubber, solid rubber; the flail rebounded. They were used to Mr. Bodiham at Crome. The flail thumped on india-rubber, and as often as not the rubber slept.
      (A. Huxley, Chrome Yellow)

IX. I drew a great security in this particular from her mere smooth aspect. There was nothing in her fresh face to pass on to others my horrible confidences. She believed me, I was sure, absolutely: if she hadn't I don't know what would have become of me, for I couldn't have borne the business alone. But she was a magnificent monument to the blessing of a want of imagination, and if she could see in our little charges nothing but their beauty and amiability, their happiness and cleverness, she had no direct communication with the sources of my trouble.
      (Henry James, The Turn of the Screw)

X. "There's the scarlet thread of murder running through the colourless skein of life, and our duty is to unravel it, and isolate it, and expose every inch of it. And now for lunch, and then for Norman Neruda. Her attack and her bowing are splendid."
      (Doyle, A Study in Scarlet)

I suppose your friend could dispute that last one, because it's part of a fictional character's quotation, and therefore not bound to the rules of grammar. Still, I stand by the others I've excerpted. And besides, do you really want to argue with Sherlock Holmes?

By the way, a good way to find more is by searching for strings like . But or . And and making sure the "Match Case" option is set.